| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94365 |
2019-01-18T01:37:34 Z |
fjzzq2002 |
Game (IOI13_game) |
C++14 |
|
13000 ms |
2832 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ull gcd(ull a,ull b)
{
ull t;
while(b)
t=a%b,a=b,b=t;
return a;
/*
#define ctz __builtin_ctzll
int shift = ctz(a | b);
b >>= ctz(b);
while (a) {
a >>= ctz(a);
if (a < b) swap(a, b);
a -= b;
}
return b << shift;
#undef ctz*/
}
#define SS 2600003
int an=0,ch[SS][2],sz[SS],xx[SS],R;
ull vv[SS],ss[SS];
void upd(int x)
{
sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
ss[x]=gcd(gcd(vv[x],ss[ch[x][0]]),ss[ch[x][1]]);
}
int merge(int a,int b)
{
if(a&&b);else return a^b;
if(sz[a]>sz[b])
{
ch[a][1]=merge(ch[a][1],b),upd(a);
return a;
}
else
{
ch[b][0]=merge(a,ch[b][0]),upd(b);
return b;
}
}
void split(int x,int u,int& a,int& b)
{
// cerr<<x<<","<<u<<","<<a<<","<<b<<"\n";
if(x==0) {a=b=0; return;}
if(xx[x]<=u)
a=x, split(ch[a][1],u,ch[a][1],b), upd(a);
else
b=x, split(ch[b][0],u,a,ch[b][0]), upd(b);
}
void edt(int& u,int x,ull v)
{
// cerr<<"E+\n";
int A,B,C;
split(u,x-1,A,B);
split(B,x,B,C);
// cerr<<"S\n";
if(!B) B=++an,sz[B]=1,xx[B]=x;
else assert(sz[B]==1);
vv[B]=ss[B]=v;
B=merge(B,C);
u=merge(A,B);
// cerr<<"E-\n";
}
ull qry(int& u,int l,int r)
{
int A,B,C;
split(u,l-1,A,B);
split(B,r,B,C);
ull rs=ss[B];
B=merge(B,C);
u=merge(A,B);
return rs;
}
int seg_ch[SS][2],seg_ps[SS],sn=0,ro;
void edt(int& x,int l,int r,int p,int q,ull v)
{
// cerr<<x<<"?\n";
if(!x) x=++sn; edt(seg_ps[x],q,v);
if(l==r) return;
int m=(l+r)>>1;
if(p<=m) edt(ch[x][0],l,m,p,q,v);
else edt(ch[x][1],m+1,r,p,q,v);
}
ull qry(int x,int l,int r,int pl,int pr,int sl,int sr)
{
if(r<pl||pr<l||!x||pl>pr) return 0;
if(pl<=l&&r<=pr) return qry(seg_ps[x],sl,sr);
int m=(l+r)>>1;
return gcd(qry(ch[x][0],l,m,pl,pr,sl,sr),
qry(ch[x][1],m+1,r,pl,pr,sl,sr));
}
ull t[233][233];
void init(int R_, int C_) {
R=R_;
}
void update(int P, int Q, long long K) {
t[P][Q]=K;
}
long long calculate(int P, int Q, int U, int V) {
ull w=0;
for(int x=P;x<=U;++x)
for(int y=Q;y<=V;++y)
w=gcd(w,t[x][y]);
return w;
}
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;
^~~
game.cpp: In function 'void edt(int&, int, int, int, int, ull)':
game.cpp:85:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(!x) x=++sn; edt(seg_ps[x],q,v);
^~
game.cpp:85:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(!x) x=++sn; edt(seg_ps[x],q,v);
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Execution timed out |
13074 ms |
2272 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
508 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Execution timed out |
13078 ms |
2832 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Execution timed out |
13045 ms |
2220 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
508 KB |
Output is correct |
| 10 |
Correct |
2 ms |
424 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Execution timed out |
13060 ms |
2024 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
