oj.uz

Submission #349872

# Submission time Handle Problem Language Result Execution time Memory
349872 2021-01-18T15:07:49 Z beksultan04 Game (IOI13_game) C++14
37 / 100
 1571 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.resize(R+R, vector <lol> (C+C));
}


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);
}
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));
    }
}

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) {
    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, 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)':
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)':
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 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 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 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 887 ms 129716 KB Output is correct
5 Correct 657 ms 130100 KB Output is correct
6 Correct 771 ms 128748 KB Output is correct
7 Correct 769 ms 128748 KB Output is correct
8 Correct 682 ms 128876 KB Output is correct
9 Correct 778 ms 128748 KB Output is correct
10 Correct 720 ms 128748 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 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 2 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 1162 ms 129832 KB Output is correct
13 Correct 1545 ms 126588 KB Output is correct
14 Runtime error 141 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 1792 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 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 2 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 921 ms 129860 KB Output is correct
13 Correct 608 ms 130100 KB Output is correct
14 Correct 764 ms 128876 KB Output is correct
15 Correct 750 ms 128824 KB Output is correct
16 Correct 711 ms 128748 KB Output is correct
17 Correct 761 ms 128876 KB Output is correct
18 Correct 699 ms 128748 KB Output is correct
19 Correct 1144 ms 129828 KB Output is correct
20 Correct 1534 ms 126568 KB Output is correct
21 Runtime error 150 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 0 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 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 1 ms 1644 KB Output is correct
12 Correct 870 ms 129716 KB Output is correct
13 Correct 619 ms 130160 KB Output is correct
14 Correct 764 ms 128748 KB Output is correct
15 Correct 817 ms 128748 KB Output is correct
16 Correct 669 ms 128748 KB Output is correct
17 Correct 769 ms 128748 KB Output is correct
18 Correct 724 ms 128748 KB Output is correct
19 Correct 1100 ms 129876 KB Output is correct
20 Correct 1571 ms 126536 KB Output is correct
21 Runtime error 165 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -