| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 399582 |
2021-05-06T07:01:28 Z |
cfalas |
Game (IOI13_game) |
C++14 |
|
487 ms |
12508 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;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
244 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
487 ms |
12508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
