oj.uz

Submission #349878

# Submission time Handle Problem Language Result Execution time Memory
349878 2021-01-18T15:15:19 Z tengiz05 Game (IOI13_game) C++17
63 / 100
 2474 ms 202536 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;
  	if(min(R,C) <= 100)der.assign(R+R-1, vector <lol> (C+C-1));
    else der.assign(min(5000,R+R-1), vector <lol> (min(5000,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:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int m = ly+ry>>1;
      |                 ~~^~~
game.cpp: In function 'void update_x(int, int, int, int, int, long long int)':
game.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         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:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int m = ly+ry>>1;
      |             ~~^~~
game.cpp: In function 'long long int gcd_x(int, int, int, int, int, int, int)':
game.cpp:85:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         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 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 2 ms 1516 KB Output is correct
10 Correct 2 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 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1110 ms 126752 KB Output is correct
5 Correct 777 ms 126900 KB Output is correct
6 Correct 901 ms 125676 KB Output is correct
7 Correct 892 ms 125676 KB Output is correct
8 Correct 794 ms 125676 KB Output is correct
9 Correct 933 ms 125676 KB Output is correct
10 Correct 859 ms 125676 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.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 2 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1515 ms 129868 KB Output is correct
13 Correct 1924 ms 126600 KB Output is correct
14 Correct 1295 ms 196996 KB Output is correct
15 Correct 2353 ms 197040 KB Output is correct
16 Correct 309 ms 196972 KB Output is correct
17 Correct 2234 ms 197836 KB Output is correct
18 Correct 2474 ms 197460 KB Output is correct
19 Correct 2416 ms 197612 KB Output is correct
20 Correct 2307 ms 197100 KB Output is correct
21 Correct 0 ms 364 KB Output is correct

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 2 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 2 ms 1516 KB Output is correct
10 Correct 3 ms 1664 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 1753 ms 126556 KB Output is correct
13 Correct 1151 ms 126964 KB Output is correct
14 Correct 1306 ms 125740 KB Output is correct
15 Correct 1344 ms 125676 KB Output is correct
16 Correct 1203 ms 125660 KB Output is correct
17 Correct 1338 ms 125692 KB Output is correct
18 Correct 1267 ms 125724 KB Output is correct
19 Correct 2221 ms 129808 KB Output is correct
20 Correct 2270 ms 126448 KB Output is correct
21 Correct 1300 ms 200840 KB Output is correct
22 Correct 2385 ms 201472 KB Output is correct
23 Correct 310 ms 201276 KB Output is correct
24 Correct 2124 ms 202372 KB Output is correct
25 Correct 2439 ms 202208 KB Output is correct
26 Correct 2383 ms 202536 KB Output is correct
27 Correct 2239 ms 202284 KB Output is correct
28 Runtime error 3 ms 620 KB Execution killed with signal 6 (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 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 1 ms 1516 KB Output is correct
12 Correct 1108 ms 126752 KB Output is correct
13 Correct 774 ms 126900 KB Output is correct
14 Correct 933 ms 125676 KB Output is correct
15 Correct 921 ms 125676 KB Output is correct
16 Correct 846 ms 125804 KB Output is correct
17 Correct 928 ms 125676 KB Output is correct
18 Correct 874 ms 125676 KB Output is correct
19 Correct 1488 ms 129900 KB Output is correct
20 Correct 1922 ms 126440 KB Output is correct
21 Correct 1284 ms 200556 KB Output is correct
22 Correct 2370 ms 200752 KB Output is correct
23 Correct 306 ms 200684 KB Output is correct
24 Correct 2147 ms 201292 KB Output is correct
25 Correct 2357 ms 201536 KB Output is correct
26 Correct 2360 ms 201744 KB Output is correct
27 Correct 2331 ms 201008 KB Output is correct
28 Runtime error 3 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -