oj.uz

Submission #93148

# Submission time Handle Problem Language Result Execution time Memory
93148 2019-01-06T15:22:08 Z Bodo171 Game (IOI13_game) C++14
63 / 100
 2601 ms 32972 KB 
#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#define mp make_pair
using namespace std;

struct aint
{
    aint *ls,*rs,*nxt;
    long long val;
    bool ok;
    aint()
    {
        ls=rs=0;nxt=0;
        val=0;ok=0;
    }
};
static aint *rad,*arb[40005];
static long long ans;
static int Rowss,Columnss;
static int X1,Y1,X2,Y2;
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;
}

void init(int R, int C) {
    Rowss=R;Columnss=C;
    for(int i=1;i<=4*R;i++)
        arb[i]=new aint;
    rad=new aint;
}
void updY(aint* &nod,int l,int r,int poz,long long value)
{
    if(l==r)
    {
        nod->val=value;
        return;
    }
     int m=(l+r)/2;
     if(poz<=m)
    {
        if(!nod->ls) nod->ls=new aint;
        updY(nod->ls,l,m,poz,value);
    }
    else
    {
        if(!nod->rs) nod->rs=new aint;
        updY(nod->rs,m+1,r,poz,value);
    }
    nod->val=0;
    if(nod->ls) nod->val=gcd(nod->val,nod->ls->val);
    if(nod->rs) nod->val=gcd(nod->val,nod->rs->val);
}
void qrY(aint* &nod,int l,int r)
{
    if(Y1<=l&&r<=Y2)
    {
        ans=1LL*gcd(ans,nod->val);
        return;
    }
    int m=(l+r)/2;
    if(Y1<=m&&nod->ls) qrY(nod->ls,l,m);
    if(m<Y2&&nod->rs) qrY(nod->rs,m+1,r);
}
long long aux;
void updX(int nod,int l,int r,int poz,int y,long long value)
{
    updY(arb[nod],1,Columnss,y,value);
    if(l==r)
    {
        updY(arb[nod],1,Columnss,y,value);
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) updX(2*nod,l,m,poz,y,value);
    else updX(2*nod+1,m+1,r,poz,y,value);
    ans=0;Y1=Y2=y;
    qrY(arb[2*nod],1,Columnss);
    aux=ans;ans=0;
    qrY(arb[2*nod+1],1,Columnss);
    updY(arb[nod],1,Columnss,y,gcd(aux,ans));
}

void qrX(int nod,int l,int r)
{
    if(X1<=l&&r<=X2)
    {
        qrY(arb[nod],1,Columnss);
        return;
    }
    int m=(l+r)/2;
    if(X1<=m) qrX(2*nod,l,m);
    if(m<X2) qrX(2*nod+1,m+1,r);
}
void update(int P, int Q, long long K) {
    P++,Q++;
    updX(1,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(1,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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 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 3 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 256 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 735 ms 18732 KB Output is correct
5 Correct 441 ms 17976 KB Output is correct
6 Correct 647 ms 15176 KB Output is correct
7 Correct 728 ms 14972 KB Output is correct
8 Correct 425 ms 9976 KB Output is correct
9 Correct 645 ms 15108 KB Output is correct
10 Correct 518 ms 14584 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 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 3 ms 504 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 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 1332 ms 24580 KB Output is correct
13 Correct 1981 ms 12856 KB Output is correct
14 Correct 299 ms 6268 KB Output is correct
15 Correct 2352 ms 17288 KB Output is correct
16 Correct 333 ms 31164 KB Output is correct
17 Correct 1105 ms 21624 KB Output is correct
18 Correct 2241 ms 32756 KB Output is correct
19 Correct 1682 ms 32944 KB Output is correct
20 Correct 1277 ms 32120 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 3 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 508 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 3 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 720 ms 19032 KB Output is correct
13 Correct 459 ms 18244 KB Output is correct
14 Correct 603 ms 15324 KB Output is correct
15 Correct 701 ms 15092 KB Output is correct
16 Correct 399 ms 10236 KB Output is correct
17 Correct 669 ms 15192 KB Output is correct
18 Correct 564 ms 14712 KB Output is correct
19 Correct 1349 ms 25024 KB Output is correct
20 Correct 2152 ms 13028 KB Output is correct
21 Correct 301 ms 6200 KB Output is correct
22 Correct 2318 ms 17208 KB Output is correct
23 Correct 339 ms 31300 KB Output is correct
24 Correct 1128 ms 21452 KB Output is correct
25 Correct 2601 ms 32736 KB Output is correct
26 Correct 1957 ms 32972 KB Output is correct
27 Correct 1457 ms 32212 KB Output is correct
28 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 3 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 3 ms 508 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 372 KB Output is correct
12 Correct 694 ms 19832 KB Output is correct
13 Correct 450 ms 18684 KB Output is correct
14 Correct 647 ms 15544 KB Output is correct
15 Correct 755 ms 15480 KB Output is correct
16 Correct 429 ms 10528 KB Output is correct
17 Correct 701 ms 15612 KB Output is correct
18 Correct 580 ms 15112 KB Output is correct
19 Correct 1355 ms 25260 KB Output is correct
20 Correct 1946 ms 12720 KB Output is correct
21 Correct 303 ms 6264 KB Output is correct
22 Correct 2499 ms 17312 KB Output is correct
23 Correct 337 ms 31352 KB Output is correct
24 Correct 1039 ms 21368 KB Output is correct
25 Correct 2490 ms 32664 KB Output is correct
26 Correct 1831 ms 32824 KB Output is correct
27 Correct 1334 ms 32220 KB Output is correct
28 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -