# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
399583 |
2021-05-06T07:04:44 Z |
cfalas |
게임 (IOI13_game) |
C++14 |
|
4892 ms |
100612 KB |
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
int t, n;
vi a, b;
static int M;
//static map<int, map<ii, int> > mapper;
long long gcd(long long X, long long Y) {
//return X + Y;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
template<typename Q>
struct seg_tree_2d{
template<typename T>
struct seg_tree{
T val=0;
seg_tree* left=nullptr;
seg_tree* right=nullptr;
// chain compression
T pos=-1;
T RAND_VALUE=0;
void print(int l=0, int r=M-1){
cout<<"("<<l<<" "<<r<<": "<<val<<") ";
if(left!=nullptr) left->print(l, MID);
if(right!=nullptr) left->print(MID+1, r);
}
void update(int x, T val_n, int l=0, int r=M-1){
if(x==l && r==x) val = val_n;
else if(x<l || r<x) return;
else{
if(pos>=0){ // already compressed chain, need to push
if(pos>MID){
right = new seg_tree();
right->pos = pos;
right->val = val;
}
else{
left = new seg_tree();
left->pos = pos;
left->val = val;
}
pos=-1;
}
if(x<=MID){
if(left==nullptr) left = new seg_tree(), left->pos = x, left->val = val_n;
else left->update(x,val_n,l,MID);
}
else{
if(right==nullptr) right = new seg_tree(), right->pos = x, right->val = val_n;
else right->update(x,val_n,MID+1, r);
}
T g = 0;
if(left!=nullptr) g = gcd(g, left->val);
if(right!=nullptr) g = gcd(g, right->val);
val = g;
}
}
T query(int rl, int rr, int l=0, int r=M-1){
if(rl<=l && r<=rr) return val;
else if(rl>r || l>rr) return RAND_VALUE;
else{
if(pos>=0 && rl<=pos && pos<=rr) return val;
else if(pos>=0) return 0;
T g = 0;
if(left!=nullptr) g = gcd(g, left->query(rl,rr,l,MID));
if(right!=nullptr) g = gcd(g, right->query(rl,rr,MID+1,r));
return g;
}
}
};
seg_tree<Q> val;
seg_tree_2d* left=nullptr;
seg_tree_2d* right=nullptr;
static inline int N;
Q RAND_VALUE_2d=0;
void print(int l=0, int r=N-1){
cout<<"L R "<<l<<" "<<r<<" "<<endl;
//seg2d[ind].val->print();
cout<<endl;
if(left!=nullptr) left->print(l, MID);
if(right!=nullptr) right->print(MID+1, r);
}
void update(int y, int x, Q val_n, int l=0, int r=N-1){
if(y==l && y==r) val.update(x, val_n);
else if(y<l || r<y) return;
else{
if(y<=MID){
if(left==nullptr) left = new seg_tree_2d;
left->update(y,x,val_n,l,MID);
}
else{
if(right==nullptr) right = new seg_tree_2d;
right->update(y,x,val_n,MID+1,r);
}
Q g = 0;
if(left!=nullptr) g = gcd(g, left->val.query(x, x));
if(right!=nullptr) g = gcd(g, right->val.query(x, x));
if(val.query(x, x)!= g){
val.update(x, g);
}
//merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
}
}
Q query(int rl, int rr, int xl, int xr, int l=0, int r=N-1){
if(rl<=l && r<=rr) return val.query(xl, xr);
else if(rl>r || l>rr) return RAND_VALUE_2d;
else{
Q g = 0;
if(left!=nullptr) g = gcd(g, left->query(rl, rr, xl, xr,l,MID));
if(right!=nullptr) g = gcd(g, right->query(rl,rr,xl,xr,MID+1,r));
return g;
}
}
};
seg_tree_2d<ll> seg;
void init(int R, int C) {
M = R;
seg.N = C;
}
void update(int P, int Q, long long K) {
seg.update(Q,P,K);
}
long long calculate(int P, int Q, int U, int V) {
return seg.query(Q,V,P,U);
}
Compilation message
game.cpp:114:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
114 | static inline int N;
| ^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
448 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
491 ms |
12548 KB |
Output is correct |
5 |
Correct |
495 ms |
13624 KB |
Output is correct |
6 |
Correct |
594 ms |
10988 KB |
Output is correct |
7 |
Correct |
693 ms |
10608 KB |
Output is correct |
8 |
Correct |
414 ms |
7492 KB |
Output is correct |
9 |
Correct |
663 ms |
10680 KB |
Output is correct |
10 |
Correct |
638 ms |
10412 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
817 ms |
13248 KB |
Output is correct |
13 |
Correct |
1391 ms |
6828 KB |
Output is correct |
14 |
Correct |
317 ms |
1840 KB |
Output is correct |
15 |
Correct |
1672 ms |
8856 KB |
Output is correct |
16 |
Correct |
224 ms |
12384 KB |
Output is correct |
17 |
Correct |
706 ms |
7960 KB |
Output is correct |
18 |
Correct |
1265 ms |
13012 KB |
Output is correct |
19 |
Correct |
1037 ms |
13264 KB |
Output is correct |
20 |
Correct |
977 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
493 ms |
13508 KB |
Output is correct |
13 |
Correct |
483 ms |
13852 KB |
Output is correct |
14 |
Correct |
619 ms |
11396 KB |
Output is correct |
15 |
Correct |
698 ms |
11244 KB |
Output is correct |
16 |
Correct |
421 ms |
7792 KB |
Output is correct |
17 |
Correct |
652 ms |
11112 KB |
Output is correct |
18 |
Correct |
631 ms |
10780 KB |
Output is correct |
19 |
Correct |
817 ms |
13432 KB |
Output is correct |
20 |
Correct |
1405 ms |
6844 KB |
Output is correct |
21 |
Correct |
305 ms |
2056 KB |
Output is correct |
22 |
Correct |
1677 ms |
9112 KB |
Output is correct |
23 |
Correct |
226 ms |
12736 KB |
Output is correct |
24 |
Correct |
723 ms |
8236 KB |
Output is correct |
25 |
Correct |
1225 ms |
13024 KB |
Output is correct |
26 |
Correct |
1082 ms |
13480 KB |
Output is correct |
27 |
Correct |
1076 ms |
12412 KB |
Output is correct |
28 |
Correct |
571 ms |
45868 KB |
Output is correct |
29 |
Correct |
1290 ms |
41428 KB |
Output is correct |
30 |
Correct |
3805 ms |
41312 KB |
Output is correct |
31 |
Correct |
3537 ms |
33572 KB |
Output is correct |
32 |
Correct |
680 ms |
1796 KB |
Output is correct |
33 |
Correct |
884 ms |
5728 KB |
Output is correct |
34 |
Correct |
295 ms |
38336 KB |
Output is correct |
35 |
Correct |
929 ms |
20332 KB |
Output is correct |
36 |
Correct |
1864 ms |
38708 KB |
Output is correct |
37 |
Correct |
1463 ms |
39060 KB |
Output is correct |
38 |
Correct |
1453 ms |
38388 KB |
Output is correct |
39 |
Correct |
1193 ms |
30080 KB |
Output is correct |
40 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
502 ms |
12504 KB |
Output is correct |
13 |
Correct |
485 ms |
12864 KB |
Output is correct |
14 |
Correct |
577 ms |
10180 KB |
Output is correct |
15 |
Correct |
692 ms |
9892 KB |
Output is correct |
16 |
Correct |
424 ms |
6808 KB |
Output is correct |
17 |
Correct |
642 ms |
9900 KB |
Output is correct |
18 |
Correct |
634 ms |
9568 KB |
Output is correct |
19 |
Correct |
814 ms |
12364 KB |
Output is correct |
20 |
Correct |
1406 ms |
6208 KB |
Output is correct |
21 |
Correct |
303 ms |
964 KB |
Output is correct |
22 |
Correct |
1653 ms |
8036 KB |
Output is correct |
23 |
Correct |
230 ms |
11592 KB |
Output is correct |
24 |
Correct |
697 ms |
7120 KB |
Output is correct |
25 |
Correct |
1254 ms |
12064 KB |
Output is correct |
26 |
Correct |
1055 ms |
11976 KB |
Output is correct |
27 |
Correct |
990 ms |
11412 KB |
Output is correct |
28 |
Correct |
585 ms |
45980 KB |
Output is correct |
29 |
Correct |
1281 ms |
41464 KB |
Output is correct |
30 |
Correct |
3807 ms |
41104 KB |
Output is correct |
31 |
Correct |
3539 ms |
33696 KB |
Output is correct |
32 |
Correct |
681 ms |
1896 KB |
Output is correct |
33 |
Correct |
886 ms |
5536 KB |
Output is correct |
34 |
Correct |
305 ms |
38340 KB |
Output is correct |
35 |
Correct |
918 ms |
20324 KB |
Output is correct |
36 |
Correct |
1836 ms |
38768 KB |
Output is correct |
37 |
Correct |
1443 ms |
38812 KB |
Output is correct |
38 |
Correct |
1441 ms |
38300 KB |
Output is correct |
39 |
Correct |
815 ms |
100612 KB |
Output is correct |
40 |
Correct |
2035 ms |
84300 KB |
Output is correct |
41 |
Correct |
4892 ms |
87580 KB |
Output is correct |
42 |
Correct |
4484 ms |
70800 KB |
Output is correct |
43 |
Correct |
539 ms |
82336 KB |
Output is correct |
44 |
Correct |
969 ms |
1552 KB |
Output is correct |
45 |
Correct |
1191 ms |
29876 KB |
Output is correct |
46 |
Correct |
2488 ms |
82476 KB |
Output is correct |
47 |
Correct |
2473 ms |
82684 KB |
Output is correct |
48 |
Correct |
2393 ms |
81988 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |