oj.uz

Submission #349876

# Submission time Handle Problem Language Result Execution time Memory
349876 2021-01-18T15:13:15 Z tengiz05 Game (IOI13_game) C++17
10 / 100
 1945 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.assign(min(7000,R+R-1), vector <lol> (min(7000,C+C-1)));
}
 
 
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 1 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 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 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 0 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 Runtime error 6 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 2 ms 1516 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 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1534 ms 129736 KB Output is correct
13 Correct 1945 ms 126464 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 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 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 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Runtime error 5 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 420 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Runtime error 5 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -