oj.uz

Submission #349879

# Submission time Handle Problem Language Result Execution time Memory
349879 2021-01-18T15:17:27 Z beksultan04 Game (IOI13_game) C++14
63 / 100
 2496 ms 256000 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;
    if (min(R,C) <= 100)
        der.resize((R<<2),vector <lol> (C<<2));
    else
        der.resize((5000),vector <lol> (5000));
}

lol k;
void update_y(int vx,int lx,int rx,int vy,int ly,int ry,int x,int y){
    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);
        else
            update_y(vx,lx,rx,vy<<1,ly,m,x,y);
        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){
    if (lx != rx){
        int m = lx+rx>>1;
        if (x > m){
            update_x((vx<<1)+1,m+1,rx,x,y);
        }
        else {
            update_x((vx<<1),lx,m,x,y);
        }
    }
    update_y(vx,lx,rx,1,0,m,x,y);
}



void update(int P, int Q, lol K) {
    k = K;
    update_x(1,0,n,P,Q);

}



int xx1,xx2,yy1,yy2;
lol gcd_y(int &vx,int vy,int ly,int ry){
    if (yy1 > ry || yy2 < ly)ret 0;
    if (yy1 <= ly && ry <= yy2)ret der[vx][vy];
    int m = ly+ry>>1;
    ret __gcd(gcd_y(vx,vy<<1,ly,m),gcd_y(vx,(vy<<1)+1,m+1,ry));
}

lol gcd_x(int vx,int lx,int rx){
    if (xx1 > rx || xx2 < lx)ret 0;
    if (xx1 <= lx && rx <= xx2){
        ret gcd_y(vx,1,0,m);
    }
    else {
        int m = lx+rx>>1;
        ret __gcd(gcd_x(vx<<1,lx,m),gcd_x((vx<<1)+1,m+1,rx));
    }
}



lol calculate(int P, int Q, int U, int V) {
    xx1 = P;
    yy1 = Q;
    xx2 = U;
    yy2 = V;
    ret gcd_x(1,0,n);
}

Compilation message

game.cpp: In function 'void update_y(int, int, int, int, int, int, int, 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)':
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)':
game.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int m = ly+ry>>1;
      |             ~~^~~
game.cpp: In function 'long long int gcd_x(int, int, int)':
game.cpp:95:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         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 1644 KB Output is correct
3 Correct 2 ms 1644 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1644 KB Output is correct
6 Correct 1 ms 1644 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 1644 KB Output is correct
10 Correct 1 ms 1644 KB Output is correct
11 Correct 2 ms 1644 KB Output is correct
12 Correct 0 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 888 ms 129744 KB Output is correct
5 Correct 610 ms 130100 KB Output is correct
6 Correct 841 ms 128748 KB Output is correct
7 Correct 794 ms 128748 KB Output is correct
8 Correct 692 ms 128748 KB Output is correct
9 Correct 758 ms 128748 KB Output is correct
10 Correct 1020 ms 128772 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 1792 KB Output is correct
3 Correct 3 ms 1792 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 1644 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 2 ms 1780 KB Output is correct
10 Correct 2 ms 1644 KB Output is correct
11 Correct 2 ms 1644 KB Output is correct
12 Correct 1696 ms 200372 KB Output is correct
13 Correct 2136 ms 196992 KB Output is correct
14 Correct 1604 ms 196992 KB Output is correct
15 Correct 2496 ms 197060 KB Output is correct
16 Correct 437 ms 196972 KB Output is correct
17 Correct 2398 ms 197620 KB Output is correct
18 Correct 2132 ms 197368 KB Output is correct
19 Correct 1865 ms 197648 KB Output is correct
20 Correct 1773 ms 196868 KB Output is correct
21 Correct 1 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 1644 KB Output is correct
3 Correct 1 ms 1644 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1644 KB Output is correct
6 Correct 1 ms 1644 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 1644 KB Output is correct
10 Correct 1 ms 1644 KB Output is correct
11 Correct 2 ms 1644 KB Output is correct
12 Correct 843 ms 129844 KB Output is correct
13 Correct 622 ms 130100 KB Output is correct
14 Correct 746 ms 128748 KB Output is correct
15 Correct 749 ms 128748 KB Output is correct
16 Correct 665 ms 128748 KB Output is correct
17 Correct 744 ms 128748 KB Output is correct
18 Correct 689 ms 128748 KB Output is correct
19 Correct 1144 ms 200296 KB Output is correct
20 Correct 1574 ms 197104 KB Output is correct
21 Correct 1016 ms 196844 KB Output is correct
22 Correct 1851 ms 197228 KB Output is correct
23 Correct 304 ms 197100 KB Output is correct
24 Correct 1657 ms 197612 KB Output is correct
25 Correct 1897 ms 197484 KB Output is correct
26 Correct 1838 ms 197740 KB Output is correct
27 Correct 1766 ms 196972 KB Output is correct
28 Runtime error 395 ms 256000 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 1 ms 364 KB Output is correct
2 Correct 2 ms 1644 KB Output is correct
3 Correct 2 ms 1644 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1644 KB Output is correct
6 Correct 2 ms 1644 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 1644 KB Output is correct
10 Correct 1 ms 1644 KB Output is correct
11 Correct 1 ms 1644 KB Output is correct
12 Correct 851 ms 129844 KB Output is correct
13 Correct 598 ms 130100 KB Output is correct
14 Correct 748 ms 128748 KB Output is correct
15 Correct 745 ms 128748 KB Output is correct
16 Correct 660 ms 128820 KB Output is correct
17 Correct 742 ms 128748 KB Output is correct
18 Correct 689 ms 128748 KB Output is correct
19 Correct 1149 ms 200420 KB Output is correct
20 Correct 1567 ms 197228 KB Output is correct
21 Correct 962 ms 197024 KB Output is correct
22 Correct 1865 ms 196956 KB Output is correct
23 Correct 334 ms 196972 KB Output is correct
24 Correct 1662 ms 197644 KB Output is correct
25 Correct 1886 ms 197432 KB Output is correct
26 Correct 1856 ms 197484 KB Output is correct
27 Correct 1746 ms 197008 KB Output is correct
28 Runtime error 408 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -