oj.uz

Submission #133328

# Submission time Handle Problem Language Result Execution time Memory
133328 2019-07-20T12:13:02 Z amiratou Game (IOI13_game) C++14
36 / 100
 2906 ms 134016 KB 
#pragma GCC optimize("O3")
#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll st[8005][8005];
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void init(int R, int C) {
    n=R,m=C;
}
void update_y(int node,int l,int r,int node_x,int lx,int rx,int y,ll val){
    if(l>y||r<y)
        return ;
    if(l==r){
        if(lx==rx)st[node_x][node]=val;
        else st[node_x][node]=gcd2(st[node_x<<1][node],st[(node_x<<1)+1][node]);
        return ;
    }
    int med=((l+r)>>1);
    update_y((node<<1),l,med,node_x,lx,rx,y,val);
    update_y((node<<1)+1,med+1,r,node_x,lx,rx,y,val);
    st[node_x][node]=gcd2(st[node_x][(node<<1)],st[node_x][(node<<1)+1]);
}
void update_x(int node,int l,int r,int x,int y,ll val){
    if(l>x||r<x)
        return ;
    if(l!=r){
        int med=((l+r)>>1);
        update_x((node<<1),l,med,x,y,val);
        update_x((node<<1)+1,med+1,r,x,y,val);
    }
    update_y(1,0,m-1,node,l,r,y,val);
}
ll query_y(int node,int l,int r,int node_x,int y1,int y2){
    if(l>y2||r<y1)
        return 0LL;
    if(l>=y1&&r<=y2)
        return st[node_x][node];
    int med=((l+r)>>1);
    return gcd2(query_y((node<<1),l,med,node_x,y1,y2),query_y((node<<1)+1,med+1,r,node_x,y1,y2));
}
ll query_x(int node,int l,int r,int x1,int y1,int x2,int y2){
    if(l>x2||r<x1)
        return 0LL;
    if(l>=x1&&r<=x2)
        return query_y(1,0,m-1,node,y1,y2);
    int med=((l+r)>>1);
    return gcd2(query_x((node<<1),l,med,x1,y1,x2,y2),query_x((node<<1)+1,med+1,r,x1,y1,x2,y2));
}
void update(int P, int Q, ll K) {
    update_x(1,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return query_x(1,0,n-1,P,Q,U,V);
}

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 4 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 1276 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 1144 KB Output is correct
10 Correct 3 ms 764 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.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 Incorrect 877 ms 8980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 1272 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 1144 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 1073 ms 47608 KB Output is correct
13 Correct 2419 ms 39344 KB Output is correct
14 Correct 738 ms 8568 KB Output is correct
15 Correct 2906 ms 88444 KB Output is correct
16 Correct 358 ms 132344 KB Output is correct
17 Correct 1719 ms 114284 KB Output is correct
18 Correct 2168 ms 133780 KB Output is correct
19 Correct 2071 ms 134016 KB Output is correct
20 Correct 1887 ms 133108 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 256 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 4 ms 1272 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 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 867 ms 8904 KB Output isn't correct
13 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 4 ms 1400 KB Output is correct
3 Correct 4 ms 1276 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 1272 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 1272 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 853 ms 8892 KB Output isn't correct
13 Halted 0 ms 0 KB -