oj.uz

Submission #349866

# Submission time Handle Problem Language Result Execution time Memory
349866 2021-01-18T14:59:35 Z beksultan04 Game (IOI13_game) C++14
37 / 100
 1949 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);
}

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 3 ms 1664 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 768 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 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 1171 ms 133380 KB Output is correct
5 Correct 790 ms 133248 KB Output is correct
6 Correct 958 ms 130632 KB Output is correct
7 Correct 965 ms 130228 KB Output is correct
8 Correct 825 ms 130916 KB Output is correct
9 Correct 991 ms 130384 KB Output is correct
10 Correct 947 ms 130064 KB Output is correct
11 Correct 1 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 1664 KB Output is correct
3 Correct 2 ms 1664 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 2 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 1539 ms 133228 KB Output is correct
13 Correct 1949 ms 129768 KB Output is correct
14 Runtime error 146 ms 256004 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 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 2 ms 1644 KB Output is correct
10 Correct 2 ms 1644 KB Output is correct
11 Correct 2 ms 1644 KB Output is correct
12 Correct 1090 ms 133300 KB Output is correct
13 Correct 785 ms 133300 KB Output is correct
14 Correct 918 ms 130420 KB Output is correct
15 Correct 922 ms 130100 KB Output is correct
16 Correct 848 ms 130676 KB Output is correct
17 Correct 960 ms 130228 KB Output is correct
18 Correct 868 ms 129844 KB Output is correct
19 Correct 1506 ms 133268 KB Output is correct
20 Correct 1922 ms 129872 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 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 2 ms 1644 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 2 ms 1644 KB Output is correct
12 Correct 1133 ms 133812 KB Output is correct
13 Correct 781 ms 133872 KB Output is correct
14 Correct 938 ms 130924 KB Output is correct
15 Correct 919 ms 130468 KB Output is correct
16 Correct 810 ms 131252 KB Output is correct
17 Correct 907 ms 130612 KB Output is correct
18 Correct 866 ms 130304 KB Output is correct
19 Correct 1749 ms 133512 KB Output is correct
20 Correct 1913 ms 130228 KB Output is correct
21 Runtime error 159 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -