oj.uz

Submission #140231

# Submission time Handle Problem Language Result Execution time Memory
140231 2019-08-02T10:21:53 Z amiratou Game (IOI13_game) C++14
63 / 100
 3287 ms 133932 KB 
#include "game.h"
#include <bits/stdc++.h>
#define ll long long

ll st[8005][8005],st2[45][400005],n,m;
using namespace std;

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 update_y2(int ny,int ly,int ry,int nx,int lx,int rx,int y,ll val){
    if(ly>y||ry<y)
        return ;
    if(ly==ry){
        if(lx==rx)st2[nx][ny]=val;
        else st2[nx][ny]=gcd2(st2[nx*2][ny],st2[nx*2+1][ny]);
        return ;
    }
    int med=(ly+ry)>>1;
    update_y2(ny*2,ly,med,nx,lx,rx,y,val);
    update_y2(ny*2+1,med+1,ry,nx,lx,rx,y,val);
    st2[nx][ny]=gcd2(st2[nx][ny*2],st2[nx][ny*2+1]);
}
void update_x2(int nx,int lx,int rx,int x,int y,ll val){
    if(lx>x||rx<x)
        return ;
    if(lx!=rx){
        int med=(lx+rx)>>1;
        update_x2(nx*2,lx,med,x,y,val);
        update_x2(nx*2+1,med+1,rx,x,y,val);
    }
    update_y2(1,0,m-1,nx,lx,rx,y,val);
}
void update_y(int ny,int ly,int ry,int nx,int lx,int rx,int y,ll val){
    if(ly>y||ry<y)
        return ;
    if(ly==ry){
        if(lx==rx)st[nx][ny]=val;
        else st[nx][ny]=gcd2(st[nx*2][ny],st[nx*2+1][ny]);
        return ;
    }
    int med=(ly+ry)>>1;
    update_y(ny*2,ly,med,nx,lx,rx,y,val);
    update_y(ny*2+1,med+1,ry,nx,lx,rx,y,val);
    st[nx][ny]=gcd2(st[nx][ny*2],st[nx][ny*2+1]);
}
void update_x(int nx,int lx,int rx,int x,int y,ll val){
    if(lx>x||rx<x)
        return ;
    if(lx!=rx){
        int med=(lx+rx)>>1;
        update_x(nx*2,lx,med,x,y,val);
        update_x(nx*2+1,med+1,rx,x,y,val);
    }
    update_y(1,0,m-1,nx,lx,rx,y,val);
}
ll query_y2(int ny,int ly,int ry,int nx,int y1,int y2){
    if(ly>y2||ry<y1)
        return 0LL;
    if(ly>=y1&&ry<=y2)
        return st2[nx][ny];
    int med=(ly+ry)>>1;
    return gcd2(query_y2(ny*2,ly,med,nx,y1,y2),query_y2(ny*2+1,med+1,ry,nx,y1,y2));
}
ll query_x2(int nx,int lx,int rx,int x1,int y1,int x2,int y2){
    if(lx>x2||rx<x1)
        return 0LL;
    if(lx>=x1&&rx<=x2)
        return query_y2(1,0,m-1,nx,y1,y2);
    int med=(lx+rx)>>1;
    return gcd2(query_x2(nx*2,lx,med,x1,y1,x2,y2),query_x2(nx*2+1,med+1,rx,x1,y1,x2,y2));
}
ll query_y(int ny,int ly,int ry,int nx,int y1,int y2){
    if(ly>y2||ry<y1)
        return 0LL;
    if(ly>=y1&&ry<=y2)
        return st[nx][ny];
    int med=(ly+ry)>>1;
    return gcd2(query_y(ny*2,ly,med,nx,y1,y2),query_y(ny*2+1,med+1,ry,nx,y1,y2));
}
ll query_x(int nx,int lx,int rx,int x1,int y1,int x2,int y2){
    if(lx>x2||rx<x1)
        return 0LL;
    if(lx>=x1&&rx<=x2)
        return query_y(1,0,m-1,nx,y1,y2);
    int med=(lx+rx)>>1;
    return gcd2(query_x(nx*2,lx,med,x1,y1,x2,y2),query_x(nx*2+1,med+1,rx,x1,y1,x2,y2));
}
void init(int R, int C) {
    n=R,m=C;
}

void update(int P, int Q, long long 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 376 KB Output is correct
2 Correct 2 ms 1244 KB Output is correct
3 Correct 4 ms 1400 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 404 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 504 KB Output is correct
4 Correct 987 ms 43612 KB Output is correct
5 Correct 674 ms 43340 KB Output is correct
6 Correct 919 ms 44468 KB Output is correct
7 Correct 937 ms 44340 KB Output is correct
8 Correct 751 ms 42224 KB Output is correct
9 Correct 1004 ms 44396 KB Output is correct
10 Correct 807 ms 43824 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 380 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 4 ms 1400 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 372 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 Correct 1342 ms 47684 KB Output is correct
13 Correct 2740 ms 39328 KB Output is correct
14 Correct 874 ms 8580 KB Output is correct
15 Correct 3285 ms 88424 KB Output is correct
16 Correct 374 ms 132472 KB Output is correct
17 Correct 1851 ms 114532 KB Output is correct
18 Correct 2353 ms 133900 KB Output is correct
19 Correct 2251 ms 133760 KB Output is correct
20 Correct 2078 ms 133252 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 376 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 4 ms 1400 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 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 1128 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 976 ms 43784 KB Output is correct
13 Correct 671 ms 43280 KB Output is correct
14 Correct 913 ms 44376 KB Output is correct
15 Correct 921 ms 44280 KB Output is correct
16 Correct 788 ms 42180 KB Output is correct
17 Correct 1044 ms 44288 KB Output is correct
18 Correct 800 ms 43768 KB Output is correct
19 Correct 1336 ms 47824 KB Output is correct
20 Correct 2745 ms 39380 KB Output is correct
21 Correct 866 ms 8648 KB Output is correct
22 Correct 3280 ms 88496 KB Output is correct
23 Correct 368 ms 132472 KB Output is correct
24 Correct 1941 ms 114412 KB Output is correct
25 Correct 2385 ms 133856 KB Output is correct
26 Correct 2275 ms 133640 KB Output is correct
27 Correct 2090 ms 133240 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 3 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 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 988 ms 43604 KB Output is correct
13 Correct 667 ms 43368 KB Output is correct
14 Correct 978 ms 44628 KB Output is correct
15 Correct 943 ms 44408 KB Output is correct
16 Correct 731 ms 42316 KB Output is correct
17 Correct 928 ms 44252 KB Output is correct
18 Correct 793 ms 43768 KB Output is correct
19 Correct 1335 ms 47736 KB Output is correct
20 Correct 2734 ms 39452 KB Output is correct
21 Correct 867 ms 8568 KB Output is correct
22 Correct 3287 ms 88440 KB Output is correct
23 Correct 382 ms 132472 KB Output is correct
24 Correct 1849 ms 114508 KB Output is correct
25 Correct 2326 ms 133932 KB Output is correct
26 Correct 2268 ms 133920 KB Output is correct
27 Correct 2048 ms 133544 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 -