Submission #3000254
Source Code Expand
// ref: https://arc068.contest.atcoder.jp/submissions/3000198
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8] = { 0,0,-1,1,1,1,-1,-1 };
int dy[8] = { -1,1,0,0,1,-1,1,-1 };
const int SIZE = 300050;
//ここまでテンプレ
//↓Binary Indexed Tree
struct BIT {
private:
int n;
vector<int> node;
public:
//N要素のBITを作り、すべて0で初期化する
//1-indexedであることに注意!!
BIT(int N) {
node.resize(N + 1, 0);
n = N;
}
//ノードiまでの和を計算する
int sum(int i) {
if (!i)
return 0;
return node[i] + sum(i - (i&-i));
}
//ノードiにxを足す
void add(int i, int x) {
if (i > n)
return;
node[i] += x;
add(i + (i&-i), x);
}
};
//↑Binary Indexed Tree
int main() {
int N, M;
cin >> N >> M;
//x=l,y=r
//クエリ<x,0:区間,1:質問,y>
priority_queue<tint, vector<tint>, greater<tint>> Q;
vector<unordered_set<int> > memo(M+2);
//クエリに区間を入れる
for (int i = 0; i < N; i++) {
int l, r;
cin >> l >> r;
Q.emplace(l, 0, r);
}
//クエリに質問を入れていく
for (int i = 1; i <= M; i++) {
for (int j = i; j <= M; j += i) {
int a = j - i, b = j;
//すでに入れてたら入れない
if(memo[b].find(b) == memo[b].end())
Q.emplace(b, 1, b);
if(memo[a].find(b) == memo[a].end())
Q.emplace(a, 1, b);
}
}
//BIT
BIT B(M + 2);
//クエリを処理する
vector<unordered_map<int, int> > pam(M + 2);
while(not Q.empty()){
int a, b, c;
tie(a, c, b) = Q.top(); Q.pop();
//区間クエリなら、区間を追加する
if (c == 0) {
//S.update(b,S.getsum(b,b+1)+1);
B.add(b + 1, 1);
}
//質問クエリなら、質問に答える
else {
//pam[mp(a,b)]=S.getsum(b,M+1);
pam[a][b] = B.sum(M + 1) - B.sum(b);
}
}
/*
for(pair<pint,int> P:pam)
cout<<P.first.first<<" "<<P.first.second<<" "<<P.second<<endl;
*/
//答えを求める
for (int i = 1; i <= M; i++) {
int ans = 0;
for (int j = i; j <= M; j += i) {
int a = j - i, b = j;
ans += pam[b][b] - pam[a][b];
}
cout << ans << endl;
}
system("pause");
return 0;
}
Submission Info
Submission Time
2018-08-13 03:52:52+0900
Task
E - Snuke Line
User
kurenaif
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
3073 Byte
Status
AC
Exec Time
1305 ms
Memory
100696 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:129:17: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
system("pause");
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt
All
00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
AC
2 ms
504 KB
00_example_02.txt
AC
2 ms
504 KB
01.txt
AC
2 ms
504 KB
02.txt
AC
3 ms
512 KB
03.txt
AC
3 ms
632 KB
04.txt
AC
2 ms
504 KB
05.txt
AC
7 ms
1080 KB
06.txt
AC
7 ms
1080 KB
07.txt
AC
2 ms
504 KB
08.txt
AC
4 ms
760 KB
09.txt
AC
2 ms
504 KB
10.txt
AC
2 ms
512 KB
11.txt
AC
564 ms
41052 KB
12.txt
AC
1273 ms
99680 KB
13.txt
AC
245 ms
10212 KB
14.txt
AC
201 ms
8048 KB
15.txt
AC
203 ms
7396 KB
16.txt
AC
450 ms
30688 KB
17.txt
AC
1245 ms
95832 KB
18.txt
AC
189 ms
7408 KB
19.txt
AC
1304 ms
100064 KB
20.txt
AC
1283 ms
100056 KB
21.txt
AC
1274 ms
99032 KB
22.txt
AC
1284 ms
100308 KB
23.txt
AC
1305 ms
98904 KB
24.txt
AC
1280 ms
99168 KB
25.txt
AC
283 ms
13284 KB
26.txt
AC
206 ms
7652 KB
27.txt
AC
1283 ms
99672 KB
28.txt
AC
288 ms
13292 KB
29.txt
AC
1288 ms
100320 KB
30.txt
AC
301 ms
13292 KB
31.txt
AC
1275 ms
99808 KB
32.txt
AC
297 ms
13292 KB
33.txt
AC
209 ms
8560 KB
34.txt
AC
1288 ms
100696 KB
35.txt
AC
1277 ms
99672 KB
36.txt
AC
2 ms
504 KB
37.txt
AC
1062 ms
96096 KB