oj.uz

Submission #93134

# Submission time Handle Problem Language Result Execution time Memory
93134 2019-01-06T15:00:22 Z Bodo171 Game (IOI13_game) C++14
37 / 100
 13000 ms 17524 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=0;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 updX(aint* &nod,int l,int r,int poz,int y,long long value)
{
    if(!nod->nxt) nod->nxt=new aint;
    updY(nod->nxt,1,Columnss,y,value);
    if(l==r) 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);
    }
}
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);
}
void qrX(aint* &nod,int l,int r)
{
    if(l==r)
    {
        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 376 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 256 KB Output is correct
8 Correct 2 ms 256 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 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 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1006 ms 17356 KB Output is correct
5 Correct 563 ms 17428 KB Output is correct
6 Correct 644 ms 14572 KB Output is correct
7 Correct 738 ms 14332 KB Output is correct
8 Correct 454 ms 9464 KB Output is correct
9 Correct 703 ms 14508 KB Output is correct
10 Correct 576 ms 14004 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 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 Execution timed out 13018 ms 12020 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 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 376 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 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 1016 ms 17476 KB Output is correct
13 Correct 573 ms 17524 KB Output is correct
14 Correct 679 ms 14564 KB Output is correct
15 Correct 766 ms 14328 KB Output is correct
16 Correct 558 ms 9572 KB Output is correct
17 Correct 714 ms 14512 KB Output is correct
18 Correct 640 ms 13920 KB Output is correct
19 Execution timed out 13058 ms 12472 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 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 376 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 256 KB Output is correct
8 Correct 2 ms 256 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 1008 ms 17476 KB Output is correct
13 Correct 564 ms 17504 KB Output is correct
14 Correct 688 ms 14584 KB Output is correct
15 Correct 785 ms 14328 KB Output is correct
16 Correct 452 ms 9444 KB Output is correct
17 Correct 788 ms 14440 KB Output is correct
18 Correct 653 ms 13988 KB Output is correct
19 Execution timed out 13022 ms 12524 KB Time limit exceeded
20 Halted 0 ms 0 KB -