oj.uz

답안 #349875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349875 2021-01-18T15:13:10 Z beksultan04 게임 (IOI13_game) C++14
27 / 100
 845 ms 75076 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 * 3,vector <lol> (C*3));
}

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Runtime error 1 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 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 845 ms 74820 KB Output is correct
5 Correct 596 ms 75076 KB Output is correct
6 Correct 761 ms 73068 KB Output is correct
7 Correct 736 ms 73068 KB Output is correct
8 Correct 679 ms 73068 KB Output is correct
9 Correct 731 ms 73068 KB Output is correct
10 Correct 705 ms 73068 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Runtime error 1 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Runtime error 1 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Runtime error 1 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -