| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93095 |
2019-01-06T13:03:28 Z |
Bodo171 |
Game (IOI13_game) |
C++14 |
|
2 ms |
504 KB |
#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#define mp make_pair
using namespace std;
struct punct
{
int x,y;
long long val;
};
bool byX(punct unu,punct doi)
{
return (unu.x<doi.x);
}
bool byY(punct unu,punct doi)
{
return (unu.y<doi.y);
}
long long gcd(long long X, long long Y) {
long long tmp;
if(!X) return Y;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
map < pair<int,int>, pair<int,int> > wh;
const int SQRT=505;
const int buck=225;
const int nmax=22005;
punct v[nmax];
long long ans;
int n,bucks;
struct bucket
{
long long arb[4*SQRT];
int sz,l,r;
punct a[SQRT];
void reset()
{
for(int i=1;i<=4*sz;i++)
arb[i]=0;
l=LLONG_MAX;r=0;
sz=0;
}
void baga(punct p)
{
a[++sz]=p;
l=min(p.x,l);
r=max(p.x,r);
}
void upd(int nod,int l,int r,int poz)
{
if(l==r)
{
arb[nod]=a[l].val;
return;
}
int m=(l+r)/2;
if(poz<=m)upd(2*nod,l,m,poz);
else upd(2*nod+1,m+1,r,poz);
arb[nod]=gcd(arb[2*nod],arb[2*nod+1]);
}
void update(int poz,long long newval)
{
a[poz].val=newval;
upd(1,1,sz,poz);
}
void D(int nod,int l,int r)
{
if(l==r)
{
arb[nod]=a[l].val;
return;
}
int m=(l+r)/2;
D(2*nod,l,m);
D(2*nod+1,m+1,r);
arb[nod]=gcd(arb[2*nod],arb[2*nod+1]);
}
void init(int nr_bucket)
{
sort(a+1,a+sz+1,byY);
for(int i=1;i<=sz;i++)
{
wh[mp(a[i].x,a[i].y)]={nr_bucket,i};
}
D(1,1,sz);
}
void qry(int nod,int l,int r,int st,int dr)
{
if(st<=l&&r<=dr)
{
ans=gcd(ans,arb[nod]);
return;
}
int m=(l+r)/2;
if(st<=m) qry(2*nod,l,m,st,dr);
if(m<dr) qry(2*nod+1,m+1,r,st,dr);
}
void japca(int X1,int Y1,int X2,int Y2)
{
for(int i=1;i<=sz;i++)
if(a[i].x>=X1&&a[i].x<=X2&&a[i].y>=Y1&&a[i].y<=Y2)
ans=gcd(ans,a[i].val);
}
int cb(int val)
{
int ret=0;
for(int p=9;p>=0;p--)
if(ret+(1<<p)<=sz&&a[ret+(1<<p)].y<=val)
ret+=(1<<p);
return ret;
}
void query(int st,int dr)
{
int p1,p2;
p1=cb(st-1);p2=cb(dr);
if(a[p1].y<st)
p1++;
if(p1<p2)
qry(1,1,sz,p1,p2);
}
}b[2*SQRT],libere;
void rebucket()
{
sort(v+1,v+n+1,byX);
bucks=0;libere.reset();bucks=0;
for(int cnt=1;cnt<=n;cnt+=buck)
{
bucks++;b[bucks].reset();
for(int j=cnt;j<=min(n,cnt+buck-1);j++)
{
b[bucks].baga(v[j]);
}
b[bucks].init(bucks);
}
}
void init(int R, int C) {
rebucket();
}
void update(int P, int Q, long long K) {
if(wh[mp(P,Q)].first)
{
b[wh[mp(P,Q)].first].update(wh[mp(P,Q)].second,K);
return;
}
else
{
n++;v[n]={P,Q,K};
if(n%buck==0)
{
rebucket();
}
else
{
libere.baga({P,Q,K});
}
}
}
long long calculate(int P, int Q, int U, int V) {
ans=0;
for(int i=1;i<=bucks;i++)
if(P<=b[i].l&&b[i].r<=U)
{
b[i].query(Q,V);
}
else
{
if(b[i].r>=P||b[i].l<=U)
{
b[i].japca(P,Q,U,V);
}
}
libere.japca(P,Q,U,V);
return ans;
}
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 member function 'void bucket::reset()':
game.cpp:48:11: warning: overflow in implicit constant conversion [-Woverflow]
l=LLONG_MAX;r=0;
^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
