| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 152472 |
2019-09-08T06:21:47 Z |
arnold518 |
Game (IOI13_game) |
C++14 |
|
3 ms |
504 KB |
#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;
Node1() : val(0), lc(-1), rc(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
nodes1.push_back(Node1());
//printf("???%d %d %lld\n", nodes1.back().lc, nodes1.back().rc, nodes1.back().val);
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());
//printf("???%d %d %d\n", nodes2.back().lc, nodes2.back().rc, nodes2.back().val);
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(x<=mid)
{
if(nodes1[node].lc==-1) nodes1[node].lc=newNode1();
update1(nodes1[node].lc, tl, mid, x, val);
}
else
{
if(nodes1[node].rc==-1) nodes1[node].rc=newNode1();
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;
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) nodes2[node].val=newNode1();
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) nodes2[node].lc=newNode2();
update2(nodes2[node].lc, tl, mid, y, x, val);
}
else
{
if(nodes2[node].rc==-1) nodes2[node].rc=newNode2();
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);
}
Compilation message
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:45: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:67: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:83: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:109:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:120:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:120:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:127:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:127:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:134:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:134:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
