oj.uz

Submission #93128

# Submission time Handle Problem Language Result Execution time Memory
93128 2019-01-06T14:50:11 Z Bodo171 Game (IOI13_game) C++14
37 / 100
 908 ms 12256 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,*c[105];
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<=R;i++)
        c[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 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(X1<=l&&r<=X2)
    {
        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++;
    updY(c[P],1,Columnss,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;
    for(int i=X1;i<=X2;i++)
        qrY(c[i],1,Columnss);
    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 376 KB Output is correct
3 Correct 2 ms 376 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 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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 908 ms 9848 KB Output is correct
5 Correct 508 ms 12024 KB Output is correct
6 Correct 577 ms 9748 KB Output is correct
7 Correct 701 ms 9600 KB Output is correct
8 Correct 431 ms 8312 KB Output is correct
9 Correct 682 ms 9724 KB Output is correct
10 Correct 546 ms 9224 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 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 Runtime error 2 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 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 900 ms 9684 KB Output is correct
13 Correct 513 ms 12152 KB Output is correct
14 Correct 575 ms 9720 KB Output is correct
15 Correct 671 ms 9680 KB Output is correct
16 Correct 420 ms 8164 KB Output is correct
17 Correct 646 ms 9600 KB Output is correct
18 Correct 494 ms 9336 KB Output is correct
19 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 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 256 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 905 ms 10016 KB Output is correct
13 Correct 517 ms 12256 KB Output is correct
14 Correct 575 ms 9720 KB Output is correct
15 Correct 692 ms 9628 KB Output is correct
16 Correct 415 ms 8156 KB Output is correct
17 Correct 633 ms 9720 KB Output is correct
18 Correct 504 ms 9348 KB Output is correct
19 Runtime error 2 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -