oj.uz

Submission #93102

# Submission time Handle Problem Language Result Execution time Memory
93102 2019-01-06T13:22:21 Z Bodo171 Game (IOI13_game) C++14
10 / 100
 13000 ms 4976 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=235;
const int buck=125;
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 japcheaza(int x,int y,long long newv)
{
    for(int i=1;i<=libere.sz;i++)
        if(libere.a[i].x==x&&libere.a[i].y==y)
    {
            libere.a[i].val=newv;
            return;
    }
}
void update(int P, int Q, long long K) {
    if(wh[mp(P,Q)].first)
    {
        if(wh[mp(P,Q)].first>=0)
           b[wh[mp(P,Q)].first].update(wh[mp(P,Q)].second,K);
        else japcheaza(P,Q,K);
        return;
    }
    else
    {
        n++;v[n]={P,Q,K};
        if(n%buck==0)
        {
            rebucket();
        }
        else
        {
            libere.baga({P,Q,K});
            wh[mp(P,Q)]={-1,0};
        }
    }
}

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;
           ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 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 376 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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Execution timed out 13083 ms 4920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 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 13065 ms 4552 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 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 376 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 13048 ms 4916 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 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 376 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 13100 ms 4976 KB Time limit exceeded
13 Halted 0 ms 0 KB -