oj.uz

Submission #349871

# Submission time Handle Problem Language Result Execution time Memory
349871 2021-01-18T15:07:41 Z tengiz05 Game (IOI13_game) C++17
37 / 100
 1972 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
 
vector <vector <lol> > der;
int n,m;
 
void init(int R, int C) {
    n = R-1;
    m = C-1;
    R+=R;
    C+=C;
    der.assign(R+R-1, vector <lol> (C+C-1));
}
 
 
void update_y(int vx,int lx,int rx,int vy,int ly,int ry,int x,int y,lol k){
    if (ly == ry){
        if (lx == rx){
            der[vx][vy] = k;
        }
        else
            der[vx][vy] = __gcd(der[vx<<1][vy],der[(vx<<1)+1][vy]);
    }
    else {
        int m = ly+ry>>1;
        if (m < y)
            update_y(vx,lx,rx,(vy<<1)+1,m+1,ry,x,y,k);
        else
            update_y(vx,lx,rx,vy<<1,ly,m,x,y,k);
        der[vx][vy] = __gcd(der[vx][vy<<1],der[vx][(vy<<1)+1]);
    }
}
 
void update_x(int vx,int lx,int rx,int x,int y,lol k){
    if (lx != rx){
        int m = lx+rx>>1;
        if (x > m){
            update_x((vx<<1)+1,m+1,rx,x,y,k);
        }
        else {
            update_x((vx<<1),lx,m,x,y,k);
        }
    }
    update_y(vx,lx,rx,1,0,m,x,y,k);
}
 
lol gcd_y(int vx,int lx,int rx,int vy,int ly,int ry,int x1,int y1,int x2,int y2){
    if (y1 > ry || y2 < ly)ret 0;
    if (y1 <= ly && ry <= y2)ret der[vx][vy];
    int m = ly+ry>>1;
    ret __gcd(gcd_y(vx,lx,rx,vy<<1,ly,m,x1,y1,x2,y2),gcd_y(vx,lx,rx,(vy<<1)+1,m+1,ry,x1,y1,x2,y2));
}
 
lol gcd_x(int vx,int lx,int rx,int x1,int y1,int x2,int y2){
    if (x1 > rx || x2 < lx)ret 0;
    if (x1 <= lx && rx <= x2){
        ret gcd_y(vx,lx,rx,1,0,m,x1,y1,x2,y2);
    }
    else {
        int m = lx+rx>>1;
        ret __gcd(gcd_x(vx<<1,lx,m,x1,y1,x2,y2),gcd_x((vx<<1)+1,m+1,rx,x1,y1,x2,y2));
    }
}
 
void update(int P, int Q, lol K) {
 
    update_x(1,0,n,P,Q,K);
 
}
 
 
 
lol calculate(int P, int Q, int U, int V) {
    ret gcd_x(1,0,n,P,Q,U,V);
}

Compilation message

game.cpp: In function 'void update_y(int, int, int, int, int, int, int, int, long long int)':
game.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = ly+ry>>1;
      |                 ~~^~~
game.cpp: In function 'void update_x(int, int, int, int, int, long long int)':
game.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int m = lx+rx>>1;
      |                 ~~^~~
game.cpp: In function 'long long int gcd_y(int, int, int, int, int, int, int, int, int, int)':
game.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int m = ly+ry>>1;
      |             ~~^~~
game.cpp: In function 'long long int gcd_x(int, int, int, int, int, int, int)':
game.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int m = lx+rx>>1;
      |                 ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1100 ms 126644 KB Output is correct
5 Correct 781 ms 127048 KB Output is correct
6 Correct 948 ms 125692 KB Output is correct
7 Correct 923 ms 125820 KB Output is correct
8 Correct 823 ms 125676 KB Output is correct
9 Correct 976 ms 125672 KB Output is correct
10 Correct 912 ms 125676 KB Output is correct
11 Correct 0 ms 364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 1528 ms 129772 KB Output is correct
13 Correct 1947 ms 126448 KB Output is correct
14 Runtime error 143 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 1152 ms 126632 KB Output is correct
13 Correct 781 ms 126900 KB Output is correct
14 Correct 919 ms 125676 KB Output is correct
15 Correct 957 ms 125676 KB Output is correct
16 Correct 845 ms 125676 KB Output is correct
17 Correct 949 ms 125676 KB Output is correct
18 Correct 889 ms 125676 KB Output is correct
19 Correct 1501 ms 129796 KB Output is correct
20 Correct 1972 ms 126340 KB Output is correct
21 Runtime error 152 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 2 ms 1548 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1098 ms 126736 KB Output is correct
13 Correct 802 ms 126900 KB Output is correct
14 Correct 939 ms 125640 KB Output is correct
15 Correct 935 ms 125676 KB Output is correct
16 Correct 825 ms 125676 KB Output is correct
17 Correct 990 ms 125676 KB Output is correct
18 Correct 881 ms 125676 KB Output is correct
19 Correct 1532 ms 129772 KB Output is correct
20 Correct 1923 ms 126572 KB Output is correct
21 Runtime error 143 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -