oj.uz

Submission #349874

# Submission time Handle Problem Language Result Execution time Memory
349874 2021-01-18T15:11:18 Z beksultan04 Game (IOI13_game) C++14
36 / 100
 1879 ms 132412 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
lol der[8001][8001];
int n,m;

void init(int R, int C) {
    n = R-1;
    m = C-1;
}

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:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m = ly+ry>>1;
      |                 ~~^~~
game.cpp: In function 'void update_x(int, int, int, int, int)':
game.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int m = lx+rx>>1;
      |                 ~~^~~
game.cpp: In function 'long long int gcd_y(int&, int, int, int)':
game.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int m = ly+ry>>1;
      |             ~~^~~
game.cpp: In function 'long long int gcd_x(int, int, int)':
game.cpp:91:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         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 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
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 Incorrect 824 ms 4464 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1049 ms 43584 KB Output is correct
13 Correct 1479 ms 35692 KB Output is correct
14 Correct 793 ms 7564 KB Output is correct
15 Correct 1799 ms 87500 KB Output is correct
16 Correct 281 ms 131820 KB Output is correct
17 Correct 1598 ms 112920 KB Output is correct
18 Correct 1879 ms 131968 KB Output is correct
19 Correct 1820 ms 132412 KB Output is correct
20 Correct 1698 ms 131948 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 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Incorrect 767 ms 4460 KB Output isn't correct
13 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 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Incorrect 782 ms 4416 KB Output isn't correct
13 Halted 0 ms 0 KB -