oj.uz

Submission #93434

# Submission time Handle Problem Language Result Execution time Memory
93434 2019-01-08T12:01:27 Z Bodo171 Game (IOI13_game) C++14
100 / 100
 4521 ms 56976 KB 
#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#include <ctime>
#include <cstdlib>
#define mp make_pair
using namespace std;
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;
}
static long long ans;
static int Rowss,Columnss;
static int X1,Y1,X2,Y2;
struct Treap
{
    Treap *ls,*rs;
    int pr,poz;
    long long G,sub;
    Treap()
    {
        ls=rs=0;
        pr=rand()+1;
        poz=0;
        G=sub=0;
    }
}*nil=new Treap;
void rec(Treap * &T)
{
    if(T->ls&&T->rs)T->sub=gcd(T->ls->sub,T->rs->sub);
    else T->sub=0;
    T->sub=gcd(T->sub,T->G);
}
void rotl(Treap* &T)
{
    Treap *aux=T;
    T=T->ls;
    aux->ls=T->rs;
    T->rs=aux;
    rec(T->rs);rec(T);
}
void rotr(Treap* &T)
{
    Treap *aux=T;
    T=T->rs;
    aux->rs=T->ls;
    T->ls=aux;
    rec(T->ls);rec(T);
}

void updY(Treap* &T,int poz,long long value)
{
    if(T->poz==poz)
    {
        T->G=value;
        rec(T);
        return;
    }
    if(T==nil)
    {
        T=new Treap;T->poz=poz;
        T->ls=nil;T->rs=nil;
        T->G=value;
        rec(T);
        return;
    }
    if(poz<T->poz) updY(T->ls,poz,value);
    else updY(T->rs,poz,value);
    if(T->ls->pr>T->pr) rotl(T);
    else if(T->rs->pr>T->pr) rotr(T);
    rec(T);
}
void qrY(Treap* &T,int l,int r)
{
    if(T==nil) return;
    if(T->poz>=Y1&&T->poz<=Y2)
    {
        ans=gcd(ans,T->G);
        if(l>=Y1)
        {
            ans=gcd(T->ls->sub,ans);
        }
        else
        {
            qrY(T->ls,l,T->poz);
        }
        if(r<=Y2)
        {
            ans=gcd(T->rs->sub,ans);
        }
        else
        {
            qrY(T->rs,T->poz,r);
        }
    }
    if(T->poz<Y1) qrY(T->rs,l,r);
    if(T->poz>Y2) qrY(T->ls,l,r);
}
struct aint
{
    aint *ls,*rs;
    Treap *nxt;
    aint()
    {
        ls=rs=0;nxt=0;
    }
}*rad;
void init(int R, int C) {
    Rowss=R;Columnss=C;
    rad=new aint;
    srand(time(NULL));
    nil->pr=0;
}
long long aux=0;
void print(Treap* T)
{
    if(T==nil)
        return;
    print(T->ls);
    cout<<T->poz<<' '<<T->G<<' '<<T->pr<<'\n';
    print(T->rs);
}
void updX(aint* &nod,int l,int r,int poz,int y,long long value)
{
    if(!nod->nxt)
    {
        nod->nxt=nil;
    }
    if(l==r)
    {
         updY(nod->nxt,y,value);
        return;
    }
    int m=(l+r)/2;
    if(poz<=m)
    {
        if(!nod->ls) nod->ls=new aint;
        updX(nod->ls,l,m,poz,y,value);
    }
    else
    {
        if(!nod->rs) nod->rs=new aint;
        updX(nod->rs,m+1,r,poz,y,value);
    }
    ans=0;Y1=Y2=y;
    if(nod->ls)qrY(nod->ls->nxt,0,Columnss+1);
    aux=ans;ans=0;
    if(nod->rs)qrY(nod->rs->nxt,0,Columnss+1);
    updY(nod->nxt,y,gcd(aux,ans));
}

void qrX(aint* &nod,int l,int r)
{
    if(X1<=l&&r<=X2)
    {
        if(nod->nxt) qrY(nod->nxt,1,Columnss);
        return;
    }
    int m=(l+r)/2;
    if(X1<=m&&nod->ls) qrX(nod->ls,l,m);
    if(m<X2&&nod->rs) qrX(nod->rs,m+1,r);
}
void update(int P, int Q, long long K) {
    P++,Q++;
    updX(rad,1,Rowss,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    ans=0;
    P++,Q++,U++,V++;
    X1=P;Y1=Q;X2=U;Y2=V;
    qrX(rad,1,Rowss);
    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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 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 256 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 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 856 ms 6408 KB Output is correct
5 Correct 436 ms 10520 KB Output is correct
6 Correct 734 ms 8136 KB Output is correct
7 Correct 873 ms 7928 KB Output is correct
8 Correct 487 ms 7156 KB Output is correct
9 Correct 810 ms 7968 KB Output is correct
10 Correct 823 ms 7672 KB Output is correct
11 Correct 2 ms 316 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 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 292 KB Output is correct
5 Correct 2 ms 256 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 284 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1522 ms 12140 KB Output is correct
13 Correct 1996 ms 7168 KB Output is correct
14 Correct 342 ms 5560 KB Output is correct
15 Correct 2221 ms 8268 KB Output is correct
16 Correct 307 ms 9900 KB Output is correct
17 Correct 943 ms 9036 KB Output is correct
18 Correct 1825 ms 11568 KB Output is correct
19 Correct 1519 ms 11532 KB Output is correct
20 Correct 1502 ms 11056 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 252 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 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 856 ms 10704 KB Output is correct
13 Correct 453 ms 10564 KB Output is correct
14 Correct 738 ms 8160 KB Output is correct
15 Correct 873 ms 7928 KB Output is correct
16 Correct 501 ms 7132 KB Output is correct
17 Correct 886 ms 7932 KB Output is correct
18 Correct 845 ms 7448 KB Output is correct
19 Correct 1581 ms 12144 KB Output is correct
20 Correct 1933 ms 7024 KB Output is correct
21 Correct 333 ms 5724 KB Output is correct
22 Correct 2091 ms 8200 KB Output is correct
23 Correct 304 ms 9976 KB Output is correct
24 Correct 930 ms 8948 KB Output is correct
25 Correct 1704 ms 11356 KB Output is correct
26 Correct 1512 ms 11636 KB Output is correct
27 Correct 1433 ms 10976 KB Output is correct
28 Correct 992 ms 31628 KB Output is correct
29 Correct 2029 ms 34160 KB Output is correct
30 Correct 3044 ms 24272 KB Output is correct
31 Correct 2801 ms 20228 KB Output is correct
32 Correct 451 ms 10264 KB Output is correct
33 Correct 665 ms 10480 KB Output is correct
34 Correct 447 ms 28016 KB Output is correct
35 Correct 1224 ms 21572 KB Output is correct
36 Correct 2648 ms 32248 KB Output is correct
37 Correct 2013 ms 32216 KB Output is correct
38 Correct 2343 ms 31780 KB Output is correct
39 Correct 1682 ms 27368 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.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 420 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 128 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 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 828 ms 10652 KB Output is correct
13 Correct 437 ms 10488 KB Output is correct
14 Correct 728 ms 8056 KB Output is correct
15 Correct 900 ms 7920 KB Output is correct
16 Correct 479 ms 7160 KB Output is correct
17 Correct 807 ms 7928 KB Output is correct
18 Correct 812 ms 7648 KB Output is correct
19 Correct 1613 ms 11984 KB Output is correct
20 Correct 2025 ms 7152 KB Output is correct
21 Correct 336 ms 5624 KB Output is correct
22 Correct 2199 ms 8228 KB Output is correct
23 Correct 308 ms 9848 KB Output is correct
24 Correct 1029 ms 9056 KB Output is correct
25 Correct 1760 ms 11300 KB Output is correct
26 Correct 1385 ms 11460 KB Output is correct
27 Correct 1380 ms 11040 KB Output is correct
28 Correct 907 ms 31608 KB Output is correct
29 Correct 2054 ms 34368 KB Output is correct
30 Correct 3065 ms 24188 KB Output is correct
31 Correct 2850 ms 20180 KB Output is correct
32 Correct 449 ms 10232 KB Output is correct
33 Correct 653 ms 10492 KB Output is correct
34 Correct 444 ms 27900 KB Output is correct
35 Correct 1259 ms 21556 KB Output is correct
36 Correct 2740 ms 32168 KB Output is correct
37 Correct 1998 ms 32432 KB Output is correct
38 Correct 1995 ms 31852 KB Output is correct
39 Correct 1453 ms 55036 KB Output is correct
40 Correct 3674 ms 56976 KB Output is correct
41 Correct 4521 ms 42868 KB Output is correct
42 Correct 3839 ms 34336 KB Output is correct
43 Correct 1018 ms 51740 KB Output is correct
44 Correct 627 ms 10704 KB Output is correct
45 Correct 1587 ms 27268 KB Output is correct
46 Correct 4247 ms 56024 KB Output is correct
47 Correct 3916 ms 55772 KB Output is correct
48 Correct 3251 ms 55508 KB Output is correct
49 Correct 2 ms 256 KB Output is correct