제출 #152477

#제출 시각아이디문제언어결과실행 시간메모리
152477arnold518게임 (IOI13_game)C++14
80 / 100
7360 ms256004 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int R, C; struct Node1 { ll val; int lc, rc, pos; Node1() : val(0), lc(-1), rc(-1), pos(-1) {} }; vector<Node1> nodes1; int newNode1() { nodes1.push_back(Node1()); return (int)nodes1.size()-1; } struct Node2 { int val; int lc, rc; Node2() : val(-1), lc(-1), rc(-1) {} }; vector<Node2> nodes2; int newNode2() { nodes2.push_back(Node2()); return (int)nodes2.size()-1; } void update1(int node, int tl, int tr, int x, ll val) { //printf("%d %d %d %d %lld\n", node, tl, tr, x, val); if(tl==tr) { nodes1[node].val=val; return; } int mid=tl+tr>>1; if(nodes1[node].pos!=-1) { if(nodes1[node].pos<=mid) { int t=newNode1(); nodes1[node].lc=t; nodes1[nodes1[node].lc].pos=nodes1[node].pos; nodes1[nodes1[node].lc].val=nodes1[node].val; } else { int t=newNode1(); nodes1[node].rc=t; nodes1[nodes1[node].rc].pos=nodes1[node].pos; nodes1[nodes1[node].rc].val=nodes1[node].val; } nodes1[node].pos=-1; } if(x<=mid) { if(nodes1[node].lc==-1) { int t=newNode1(); nodes1[node].lc=t; nodes1[nodes1[node].lc].pos=x; nodes1[nodes1[node].lc].val=val; } else update1(nodes1[node].lc, tl, mid, x, val); } else { if(nodes1[node].rc==-1) { int t=newNode1(); nodes1[node].rc=t; nodes1[nodes1[node].rc].pos=x; nodes1[nodes1[node].rc].val=val; } update1(nodes1[node].rc, mid+1, tr, x, val); } ll t=0; if(nodes1[node].lc!=-1) t=__gcd(t, nodes1[nodes1[node].lc].val); if(nodes1[node].rc!=-1) t=__gcd(t, nodes1[nodes1[node].rc].val); nodes1[node].val=t; } ll query1(int node, int tl, int tr, int xl, int xr) { //printf("%d %d %d %d %d\n", node, tl, tr, xl, xr); if(xr<tl || tr<xl) return 0; if(xl<=tl && tr<=xr) return nodes1[node].val; if(nodes1[node].pos!=-1) { if(xl<=nodes1[node].pos && nodes1[node].pos<=xr) return nodes1[node].val; else return 0; } int mid=tl+tr>>1; ll ret=0; if(nodes1[node].lc!=-1) ret=__gcd(ret, query1(nodes1[node].lc, tl, mid, xl, xr)); if(nodes1[node].rc!=-1) ret=__gcd(ret, query1(nodes1[node].rc, mid+1, tr, xl, xr)); return ret; } void update2(int node, int tl, int tr, int y, int x, ll val) { //printf("%d %d %d %d %d %lld\n", node, tl, tr, y, x, val); if(nodes2[node].val==-1) { int t=newNode1(); nodes2[node].val=t; } if(tl==tr) { update1(nodes2[node].val, 1, C, x, val); return; } int mid=tl+tr>>1; if(y<=mid) { if(nodes2[node].lc==-1) { int t=newNode2(); nodes2[node].lc=t; } update2(nodes2[node].lc, tl, mid, y, x, val); } else { if(nodes2[node].rc==-1) { int t=newNode2(); nodes2[node].rc=t; } update2(nodes2[node].rc, mid+1, tr, y, x, val); } ll t=0; if(nodes2[node].lc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].lc].val, 1, C, x, x)); if(nodes2[node].rc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].rc].val, 1, C, x, x)); update1(nodes2[node].val, 1, C, x, t); } ll query2(int node, int tl, int tr, int yl, int yr, int xl, int xr) { //printf("%d %d %d %d %d %d %d\n", node, tl, tr, yl, yr, xl, xr); if(yr<tl || tr<yl) return 0; if(yl<=tl && tr<=yr) { if(nodes2[node].val!=-1) return query1(nodes2[node].val, 1, C, xl, xr); else return 0; } int mid=tl+tr>>1; ll ret=0; if(nodes2[node].lc!=-1) ret=__gcd(ret, query2(nodes2[node].lc, tl, mid, yl, yr, xl, xr)); if(nodes2[node].rc!=-1) ret=__gcd(ret, query2(nodes2[node].rc, mid+1, tr, yl, yr, xl, xr)); return ret; } int root; void init(int _R, int _C) { int i, j; R=_R; C=_C; root=newNode2(); } void update(int P, int Q, ll K) { int i, j; P++; Q++; update2(root, 1, R, P, Q, K); } ll calculate(int P, int Q, int U, int V) { int i, j; P++; Q++; U++; V++; return query2(root, 1, R, P, U, Q, V); }

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'void update1(int, int, int, int, ll)':
game.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(int, int, int, int, int)':
game.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(int, int, int, int, int, ll)':
game.cpp:114:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(int, int, int, int, int, int, int)':
game.cpp:140:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:151:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:151:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:158:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:158:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:165:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:165:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...