| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 282046 |
2020-08-23T22:25:46 Z |
rqi |
Game (IOI13_game) |
C++14 |
|
1 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define bk back()
#define pb push_back
const ld PI = acos((ld)-1);
int MAXX = 1000000000;
int MAXY = 1000000000;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
pi getRang(pi a, int b, int L = 0, int R = MAXY-1){
if(L > a.f || a.s > R || L > b || b > R) return mp(-1, -1);
int M = (L+R)/2;
pi res1 = getRang(a, b, L, M);
if(res1 != mp(-1, -1)) return res1;
pi res2 = getRang(a, b, M+1, R);
if(res2 != mp(-1, -1)) return res2;
return mp(L, R);
}
struct Node{
int L, R, M;
ll val;
Node* c[2];
Node(int _L, int _R, ll _val = 0){
L = _L;
R = _R;
M = (L+R)/2;
val = _val;
}
void pull(){
val = 0;
if(c[0]) val = gcd2(val, c[0]->val);
if(c[1]) val = gcd2(val, c[1]->val);
}
void upd(int pos, ll inc){
assert(L <= pos && pos <= R);
if(L == R){
val = inc;
return;
}
if(pos <= M){
if(!c[0]){
c[0] = new Node(pos, pos, inc);
}
else{
if(c[0]->L <= pos && pos <= c[0]->R){
c[0]->upd(pos, inc);
}
else{
pi rang = getRang(mp(c[0]->L, c[0]->R), pos);
if(c[0]->R < pos){
Node* par = new Node(rang.f, rang.s);
par->c[0] = c[0];
par->c[1] = new Node(pos, pos, inc);
c[0] = par;
par->pull();
}
else{
Node* par = new Node(rang.f, rang.s);
par->c[1] = c[0];
par->c[0] = new Node(pos, pos, inc);
c[0] = par;
par->pull();
}
}
}
}
else{
if(!c[1]){
c[1] = new Node(pos, pos, inc);
}
else{
if(c[1]->L <= pos && pos <= c[1]->R){
c[1]->upd(pos, inc);
}
else{
pi rang = getRang(mp(c[1]->L, c[1]->R), pos);
if(c[1]->R < pos){
Node* par = new Node(rang.f, rang.s);
par->c[0] = c[1];
par->c[1] = new Node(pos, pos, inc);
c[1] = par;
par->pull();
}
else{
Node* par = new Node(rang.f, rang.s);
par->c[1] = c[1];
par->c[0] = new Node(pos, pos, inc);
c[1] = par;
par->pull();
}
}
}
}
// cout << "L, R, val, pos, inc: " << L << " " << R << " " << val << " " << pos << " " << inc << "\n";
// if(c[0]){
// cout << "c[0]->L, R, val: " << c[0]->L << " " << c[0]->R << " " << c[0]->val << "\n";
// }
// if(c[1]){
// cout << "c[1]->L, R, val: " << c[1]->L << " " << c[1]->R << " " << c[1]->val << "\n";
// }
pull();
//cout << "L, R, val, pos, inc: " << L << " " << R << " " << val << " " << pos << " " << inc << "\n";
}
ll query(int lo, int hi){
if(R < lo || hi < L) return 0;
if(lo <= L && R <= hi){
return val;
}
ll res = 0;
if(c[0]){
res = gcd2(res, c[0]->query(lo, hi));
}
if(c[1]){
res = gcd2(res, c[1]->query(lo, hi));
}
return res;
}
};
struct Sparse{
int L, R, M;
Node* seg;
Sparse* c[2];
Sparse(int _L, int _R){
L = _L;
R = _R;
M = (L+R)/2;
seg = new Node(0, MAXY-1, 0);
}
void upd(int x, int y, ll inc){
if(x < L || R < x) return;
//cout << "L, R, x, y, inc: " << L << " " << R << " " << x << " " << y << " " << inc << "\n";
//cout << "seg->query(0, 1): " << seg->query(0, 1) << "\n";
seg->upd(y, inc);
//cout << "seg->query(0, 1): " << seg->query(0, 1) << "\n";
if(L == R) return;
if(x <= M){
if(!c[0]) c[0] = new Sparse(L, M);
c[0]->upd(x, y, inc);
}
else{
if(!c[1]) c[1] = new Sparse(M+1, R);
c[1]->upd(x, y, inc);
}
}
ll query(int lox, int hix, int loy, int hiy){
if(R < lox || hix < L) return 0;
if(lox <= L && R <= hix){
return seg->query(loy, hiy);
}
ll res = 0;
if(c[0]){
res = gcd2(res, c[0]->query(lox, hix, loy, hiy));
}
if(c[1]){
res = gcd2(res, c[1]->query(lox, hix, loy, hiy));
}
return res;
}
};
// bool check(pi a){
// if(a.f < 0 || a.f > MAXX) return 0;
// if(a.s < 0 || a.s > MAXY) return 0;
// return 1;
// }
Sparse* seg;
void init(int R, int C) {
MAXX = R;
MAXY = C;
// pi test = getRang(mp(1, 1), 2);
// cout << test.f << " " << test.s << "\n";
seg = new Sparse(0, MAXX-1);
}
void update(int P, int Q, long long K) {
//cout << "UPDATE " << P << " " << Q << " " << K << "\n";
seg->upd(P, Q, K);
// vpi x, y;
// x.pb(mp(P, P)); y.pb(mp(Q, Q));
// int curb = 0;
// while(true){
// pi newx = x.bk;
// if((((newx.f)>>curb)&1) == 1){
// newx.f-=(1<<curb);
// }
// if((((newx.s)>>curb)&1) == 0){
// newx.s+=(1<<curb);
// }
// if(check(newx)){
// x.pb(newx);
// }
// else break;
// curb++;
// // cout << newx.f << " " << newx.s << "\n";
// // cout << "HI\n";
// // cout.flush();
// }
// curb = 0;
// while(true){
// pi newy = y.bk;
// if((((newy.f)>>curb)&1) == 1){
// newy.f-=(1<<curb);
// }
// if((((newy.s)>>curb)&1) == 0){
// newy.s+=(1<<curb);
// }
// if(check(newy)){
// y.pb(newy);
// }
// else break;
// curb++;
// }
// for(auto a: x){
// for(auto b: y){
// seg[mp(a, b)] = gcd2(seg[mp(a, b)], K);
// }
// }
}
ll calculate(int lox, int loy, int hix, int hiy) {
//cout << "QUERY " << lox << " " << hix << " " << loy << " " << hiy << "\n";
return seg->query(lox, hix, loy, hiy);
// //cout << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
// vpi x, y;
// pi curx = mp(P, U);
// pi cury = mp(Q, V);
// int curb = 0;
// while(curx.f <= curx.s){
// if(((curx.f>>curb)&1) == 1){
// x.pb(mp(curx.f, curx.f+(1<<curb)-1));
// curx.f+=(1<<curb);
// }
// if(curx.f > curx.s) break;
// if(((curx.s>>curb)&1) == 0){
// x.pb(mp(curx.s-(1<<curb)+1, curx.s));
// curx.s-=(1<<curb);
// }
// curb++;
// }
// curb = 0;
// while(cury.f <= cury.s){
// if(((cury.f>>curb)&1) == 1){
// y.pb(mp(cury.f, cury.f+(1<<curb)-1));
// cury.f+=(1<<curb);
// }
// if(cury.f > cury.s) break;
// if(((cury.s>>curb)&1) == 0){
// y.pb(mp(cury.s-(1<<curb)+1, cury.s));
// cury.s-=(1<<curb);
// }
// curb++;
// }
// ll res = 0;
// // for(auto u: x){
// // cout << u.f << " " << u.s << "\n";
// // }
// // cout << "\n";
// // for(auto u: y){
// // cout << u.f << " " << u.s << "\n";
// // }
// for(auto a: x){
// for(auto b: y){
// if(seg.count(mp(a, b))) res = gcd2(res, seg[mp(a, b)]);
// }
// }
// /* ... */
// return res;
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
372 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
