oj.uz

Submission #93149

# Submission time Handle Problem Language Result Execution time Memory
93149 2019-01-06T15:25:07 Z Bodo171 Game (IOI13_game) C++14
63 / 100
 2648 ms 257024 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;
    aint()
    {
        ls=rs=nxt=0;
        val=0;
    }
}*rad;
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;
    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=0;
void updX(aint* &nod,int l,int r,int poz,int y,long long value)
{
    if(!nod->nxt) nod->nxt=new aint;
    if(l==r)
    {
         updY(nod->nxt,1,Columnss,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,1,Columnss);
    aux=ans;ans=0;
    if(nod->rs)qrY(nod->rs->nxt,1,Columnss);
    updY(nod->nxt,1,Columnss,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 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 256 KB Output is correct
5 Correct 2 ms 256 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 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

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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 708 ms 18900 KB Output is correct
5 Correct 432 ms 18552 KB Output is correct
6 Correct 546 ms 15736 KB Output is correct
7 Correct 657 ms 15636 KB Output is correct
8 Correct 371 ms 10616 KB Output is correct
9 Correct 690 ms 15552 KB Output is correct
10 Correct 577 ms 15120 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 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 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 252 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1363 ms 23280 KB Output is correct
13 Correct 1983 ms 9672 KB Output is correct
14 Correct 262 ms 1788 KB Output is correct
15 Correct 2302 ms 13384 KB Output is correct
16 Correct 300 ms 27688 KB Output is correct
17 Correct 1249 ms 17352 KB Output is correct
18 Correct 2341 ms 28052 KB Output is correct
19 Correct 1872 ms 28328 KB Output is correct
20 Correct 1581 ms 27596 KB Output is correct
21 Correct 6 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 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 706 ms 18612 KB Output is correct
13 Correct 449 ms 18296 KB Output is correct
14 Correct 599 ms 15420 KB Output is correct
15 Correct 738 ms 15152 KB Output is correct
16 Correct 412 ms 10332 KB Output is correct
17 Correct 652 ms 15232 KB Output is correct
18 Correct 605 ms 14884 KB Output is correct
19 Correct 1451 ms 22796 KB Output is correct
20 Correct 1983 ms 9488 KB Output is correct
21 Correct 263 ms 1556 KB Output is correct
22 Correct 2323 ms 12980 KB Output is correct
23 Correct 280 ms 27384 KB Output is correct
24 Correct 1132 ms 16760 KB Output is correct
25 Correct 2053 ms 27592 KB Output is correct
26 Correct 1477 ms 27744 KB Output is correct
27 Correct 1695 ms 27028 KB Output is correct
28 Runtime error 786 ms 257024 KB Execution killed with signal 9 (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 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 256 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 687 ms 19396 KB Output is correct
13 Correct 447 ms 19372 KB Output is correct
14 Correct 637 ms 16504 KB Output is correct
15 Correct 747 ms 16188 KB Output is correct
16 Correct 411 ms 11280 KB Output is correct
17 Correct 687 ms 16460 KB Output is correct
18 Correct 576 ms 15736 KB Output is correct
19 Correct 1358 ms 23320 KB Output is correct
20 Correct 1948 ms 9880 KB Output is correct
21 Correct 262 ms 2296 KB Output is correct
22 Correct 2648 ms 13788 KB Output is correct
23 Correct 300 ms 28100 KB Output is correct
24 Correct 1179 ms 17748 KB Output is correct
25 Correct 2428 ms 28228 KB Output is correct
26 Correct 1693 ms 28476 KB Output is correct
27 Correct 1160 ms 27732 KB Output is correct
28 Runtime error 662 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -