oj.uz

Submission #133339

# Submission time Handle Problem Language Result Execution time Memory
133339 2019-07-20T12:19:46 Z amiratou Game (IOI13_game) C++14
63 / 100
 2914 ms 133904 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],st2[45][400002];
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_y2(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)st2[node_x][node]=val;
        else st2[node_x][node]=gcd2(st2[node_x<<1][node],st2[(node_x<<1)+1][node]);
        return ;
    }
    int med=((l+r)>>1);
    update_y2((node<<1),l,med,node_x,lx,rx,y,val);
    update_y2((node<<1)+1,med+1,r,node_x,lx,rx,y,val);
    st2[node_x][node]=gcd2(st2[node_x][(node<<1)],st2[node_x][(node<<1)+1]);
}
void update_x2(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_x2((node<<1),l,med,x,y,val);
        update_x2((node<<1)+1,med+1,r,x,y,val);
    }
    update_y2(1,0,m-1,node,l,r,y,val);
}
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_y2(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 st2[node_x][node];
    int med=((l+r)>>1);
    return gcd2(query_y2((node<<1),l,med,node_x,y1,y2),query_y2((node<<1)+1,med+1,r,node_x,y1,y2));
}
ll query_x2(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_y2(1,0,m-1,node,y1,y2);
    int med=((l+r)>>1);
    return gcd2(query_x2((node<<1),l,med,x1,y1,x2,y2),query_x2((node<<1)+1,med+1,r,x1,y1,x2,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) {
    if(n<=10&&m<=100000)update_x2(1,0,n-1,P,Q,K);
    else update_x(1,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    if(n<=10&&m<=100000)return query_x2(1,0,n-1,P,Q,U,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 256 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 1400 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 3 ms 504 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 821 ms 39736 KB Output is correct
5 Correct 597 ms 39836 KB Output is correct
6 Correct 853 ms 40092 KB Output is correct
7 Correct 857 ms 39928 KB Output is correct
8 Correct 688 ms 38204 KB Output is correct
9 Correct 887 ms 40056 KB Output is correct
10 Correct 717 ms 39420 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 376 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 2 ms 376 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 892 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 1074 ms 44328 KB Output is correct
13 Correct 2416 ms 36284 KB Output is correct
14 Correct 731 ms 4600 KB Output is correct
15 Correct 2901 ms 84964 KB Output is correct
16 Correct 359 ms 129012 KB Output is correct
17 Correct 1710 ms 110392 KB Output is correct
18 Correct 2165 ms 129012 KB Output is correct
19 Correct 2067 ms 129228 KB Output is correct
20 Correct 1872 ms 128248 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 380 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 3 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 3 ms 504 KB Output is correct
9 Correct 4 ms 1144 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 857 ms 39676 KB Output is correct
13 Correct 592 ms 43640 KB Output is correct
14 Correct 863 ms 44552 KB Output is correct
15 Correct 859 ms 44324 KB Output is correct
16 Correct 688 ms 42268 KB Output is correct
17 Correct 884 ms 44296 KB Output is correct
18 Correct 713 ms 43896 KB Output is correct
19 Correct 1061 ms 47736 KB Output is correct
20 Correct 2422 ms 39628 KB Output is correct
21 Correct 752 ms 8412 KB Output is correct
22 Correct 2914 ms 88520 KB Output is correct
23 Correct 360 ms 132580 KB Output is correct
24 Correct 1797 ms 114260 KB Output is correct
25 Correct 2178 ms 133616 KB Output is correct
26 Correct 2058 ms 133776 KB Output is correct
27 Correct 1896 ms 132980 KB Output is correct
28 Runtime error 33 ms 376 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 376 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 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 3 ms 504 KB Output is correct
12 Correct 844 ms 40188 KB Output is correct
13 Correct 592 ms 43440 KB Output is correct
14 Correct 853 ms 44536 KB Output is correct
15 Correct 860 ms 44488 KB Output is correct
16 Correct 718 ms 42320 KB Output is correct
17 Correct 860 ms 44364 KB Output is correct
18 Correct 719 ms 43896 KB Output is correct
19 Correct 1070 ms 47628 KB Output is correct
20 Correct 2405 ms 39492 KB Output is correct
21 Correct 730 ms 8524 KB Output is correct
22 Correct 2903 ms 88568 KB Output is correct
23 Correct 352 ms 132636 KB Output is correct
24 Correct 1699 ms 114424 KB Output is correct
25 Correct 2167 ms 133752 KB Output is correct
26 Correct 2050 ms 133904 KB Output is correct
27 Correct 1877 ms 133060 KB Output is correct
28 Runtime error 34 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -