| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167573 |
2019-12-09T03:01:45 Z |
cgiosy |
Game (IOI13_game) |
C++17 |
|
3 ms |
404 KB |
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;
int sz1=1, sz2=1;
struct T { ll x; int l, r; } X[60000000];
struct seg {
int N, root;
seg(const int n) : N(n-1) { root=0; }
ll get(int l, int r, int s, int e, int i) const {
if(!i || e<l || r<s) return 0;
if(l<=s && e<=r) return X[i].x;
if(X[i].l<0) return X[i].x;
int m=(s+e)>>1;
return gcd(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
}
ll get(int l, int r) const { return get(l, r, 0, N, root); }
ll set(int p, ll x, int s, int e, int&i) {
if(p<s || e<p) return i>0 ? X[i].x : 0;
if(i<=0) { X[i=sz1++]={x, ~p, 0}; return x; }
if(s==e) return X[i].x=x;
int m=(s+e)>>1;
if(X[i].l<0) set(~X[i].l, X[i].x, s, m, X[i].l), set(~X[i].l, X[i].x, m+1, e, X[i].r);
return X[i].x=gcd(set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r));
}
void set(int p, ll x) { set(p, x, 0, N, root); }
};
struct T2 { seg* x; int l, r; } Y[4194304];
struct seg2 {
int N, M, root;
seg2(int n, int m) : N(n-1), M(m) { root=0; }
ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
if(!i || e<l1 || r1<s) return 0;
if(l1<=s && e<=r1) return Y[i].x->get(l2, r2);
int m=(s+e)>>1;
return gcd(get(l1, r1, l2, r2, s, m, Y[i].l), get(l1, r1, l2, r2, m+1, e, Y[i].r));
}
ll get(int l1, int r1, int l2, int r2) const { return get(l1, r1, l2, r2, 0, N, root); }
ll set(int p, int q, ll x, int s, int e, int&i) {
if(p<s || e<p) return i ? Y[i].x->get(q, q) : 0;
if(!i) Y[i=sz2++].x=new seg(M);
if(s==e) {
Y[i].x->set(q, x);
return x;
}
int m=(s+e)>>1;
ll y=gcd(set(p, q, x, s, m, Y[i].l), set(p, q, x, m+1, e, Y[i].r));
Y[i].x->set(q, y);
return y;
}
void set(int p, int q, ll x) { set(p, q, x, 0, N, root); }
} *T;
void init(int R, int C) {
T=new seg2(R, C);
}
void update(int P, int Q, ll K) {
T->set(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return T->get(P, U, Q, V);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
404 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
