oj.uz

Submission #349877

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

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:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int m = ly+ry>>1;
      |                 ~~^~~
game.cpp: In function 'void update_x(int, int, int, int, int)':
game.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int m = lx+rx>>1;
      |                 ~~^~~
game.cpp: In function 'long long int gcd_y(int&, int, int, int)':
game.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int m = ly+ry>>1;
      |             ~~^~~
game.cpp: In function 'long long int gcd_x(int, int, int)':
game.cpp:92:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         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 1640 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 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 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 868 ms 129716 KB Output is correct
5 Correct 608 ms 130084 KB Output is correct
6 Correct 752 ms 128748 KB Output is correct
7 Correct 821 ms 128748 KB Output is correct
8 Correct 678 ms 128748 KB Output is correct
9 Correct 754 ms 128876 KB Output is correct
10 Correct 722 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 268 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 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 1119 ms 129876 KB Output is correct
13 Correct 1537 ms 126640 KB Output is correct
14 Runtime error 165 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 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 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 893 ms 129856 KB Output is correct
13 Correct 607 ms 130140 KB Output is correct
14 Correct 788 ms 128876 KB Output is correct
15 Correct 757 ms 128748 KB Output is correct
16 Correct 785 ms 128908 KB Output is correct
17 Correct 759 ms 128876 KB Output is correct
18 Correct 715 ms 128876 KB Output is correct
19 Correct 1107 ms 129892 KB Output is correct
20 Correct 1593 ms 126672 KB Output is correct
21 Runtime error 153 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 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 846 ms 129844 KB Output is correct
13 Correct 605 ms 130100 KB Output is correct
14 Correct 799 ms 128748 KB Output is correct
15 Correct 758 ms 128748 KB Output is correct
16 Correct 665 ms 128748 KB Output is correct
17 Correct 751 ms 128816 KB Output is correct
18 Correct 709 ms 128748 KB Output is correct
19 Correct 1106 ms 130028 KB Output is correct
20 Correct 1543 ms 126604 KB Output is correct
21 Runtime error 148 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -