| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 290104 |
2020-09-03T12:10:20 Z |
egekabas |
Game (IOI13_game) |
C++14 |
|
1 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
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;
}
int r, c, rr;
struct node{
int tl, tr;
ll val;
node *l = nullptr, *r = nullptr;
node(int tlval, int trval){
tl = tlval;
tr = trval;
val = 0;
}
node(){
tl = tr = -1;
val = 0;
}
void upd(int idx, ll nv){
if(tl == idx && tr == idx){
val = nv;
return;
}
int tm = (tl+tr)/2;
if(idx <= tm){
if(!l)
l = new node(tl, tm);
l->upd(idx, nv);
}
else{
if(!r)
r = new node(tm+1, tr);
r->upd(idx, nv);
}
ll xval = 0, yval = 0;
if(l)
xval = l->val;
if(r)
yval = r->val;
val = gcd2(xval, yval);
}
ll get(int lef, int rig){
if(tr < lef || rig < tl)
return 0;
if(lef <= tl && tr <= rig){
return val;
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(lef, rig);
if(r)
yval = r->get(lef, rig);
return gcd2(xval, yval);
}
};
struct seg{
int tl, tr;
node *val;
seg *l = nullptr, *r = nullptr;
seg(ll tval, ll rval){
tl = tval;
tr = rval;
val = new node(0, c-1);
}
seg(){}
void upd(int xidx, int yidx, ll nv){
if(xidx < tl || xidx > tr) return;
if(tl == tr){
val->upd(yidx, nv);
return;
}
int tm = (tl+tr)/2;
if(xidx <= tm){
if(!l)
l = new seg(tl, tm);
}
else{
if(!r)
r = new seg(tm+1, tr);
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(tl, tm, yidx, yidx);
if(r)
yval = r->get(tm+1, tr, yidx, yidx);
nv = gcd2(xval, yval);
val->upd(yidx, nv);
}
ll get(int xl, int xr, int yl, int yr){
if(tr < xl || xr < tl)
return 0;
if(xl <= tl && tr <= xr){
return val->get(yl, yr);
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(xl, xr, yl, yr);
if(r)
yval = r->get(xl, xr, yl, yr);
return gcd2(xval, yval);
}
};
seg root;
void init(int R, int C) {
r = rr = R;
c = C;
root = seg(0, r-1);
}
void update(int P, int Q, long long K) {
root.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return root.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]
18 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
256 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 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 |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
