# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
281779 |
2020-08-23T13:01:22 Z |
Kastanda |
Game (IOI13_game) |
C++11 |
|
1226 ms |
41976 KB |
// M
#include<bits/stdc++.h>
#include "game.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 22005 * 2, TF = 400, MXS = N * 4, NS = N * 15;
int n, m, k, segk;
map < pair < int , int > , ll > MP, TMp;
vector < pair < int , int > > V[N], VC[MXS];
vector < int > UX, VID[MXS];
ll G[NS * 2];
inline void ModifySeg(int i, ll val)
{
G[i += NS] = val;
for (; i; i >>= 1)
G[i >> 1] = __gcd(G[i], G[i ^ 1]);
}
inline ll GetSeg(int l, int r)
{
ll g = 0;
for (l += NS, r += NS; l < r; l >>= 1, r >>= 1)
{
if (l & 1) g = __gcd(g, G[l ++]);
if (r & 1) g = __gcd(g, G[-- r]);
}
return g;
}
void Build(int id = 1, int l = 0, int r = k)
{
VC[id].clear();
VID[id].clear();
if (r - l < 2)
sort(V[l].begin(), V[l].end()), VC[id] = V[l];
else
{
Build(lc, l, md);
Build(rc, md, r);
merge(VC[lc].begin(), VC[lc].end(), VC[rc].begin(), VC[rc].end(), back_inserter(VC[id]));
}
for (int i = 0; i < (int)VC[id].size(); i ++)
{
ModifySeg(segk, MP[make_pair(VC[id][i].second, VC[id][i].first)]);
VID[id].push_back(segk ++);
}
}
inline void Relax()
{
segk = 0;
memset(G, 0, sizeof(G));
UX.clear();
for (auto X : TMp)
MP[X.first] = X.second;
TMp.clear();
for (auto e : MP)
UX.push_back(e.first.first);
UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
k = (int)UX.size();
for (int i = 0; i <= k; i ++)
V[i].clear();
int ptr = 0;
for (auto e : MP)
{
while (UX[ptr] < e.first.first)
ptr ++;
V[ptr].push_back(make_pair(e.first.second, e.first.first));
}
Build();
assert(segk < NS);
}
void Update(int i, int c, ll val, int id = 1, int l = 0, int r = k)
{
int lb = lower_bound(VC[id].begin(), VC[id].end(), make_pair(c, UX[i])) - VC[id].begin();
ModifySeg(VID[id][lb], val);
if (r - l < 2)
return ;
if (i < md)
Update(i, c, val, lc, l, md);
else
Update(i, c, val, rc, md, r);
}
void init(int _n, int _m)
{
n = _n; m = _m;
Relax();
}
void update(int r, int c, ll val)
{
if (MP.count({r, c}))
{
r = lower_bound(UX.begin(), UX.end(), r) - UX.begin();
Update(r, c, val);
MP[make_pair(r, c)] = val;
}
else
{
TMp[make_pair(r, c)] = val;
if ((int)TMp.size() >= TF)
Relax();
}
}
ll Get(int le, int ri, int lq, int rq, int id = 1, int l = 0, int r = k)
{
if (ri <= l || r <= le)
return 0LL;
if (le <= l && r <= ri)
{
int lb = lower_bound(VC[id].begin(), VC[id].end(), make_pair(lq, -1)) - VC[id].begin();
int ub = lower_bound(VC[id].begin(), VC[id].end(), make_pair(rq, -1)) - VC[id].begin() - 1;
if (lb <= ub)
return GetSeg(VID[id][lb], VID[id][ub] + 1);
}
return __gcd(Get(le, ri, lq, rq, lc, l, md), Get(le, ri, lq, rq, rc, md, r));
}
inline ll Query(int a, int b, int c, int d)
{
c ++; d ++;
a = lower_bound(UX.begin(), UX.end(), a) - UX.begin();
c = lower_bound(UX.begin(), UX.end(), c) - UX.begin();
return Get(a, c, b, d);
}
ll calculate(int a, int b, int c, int d)
{
ll g = Query(a, b, c, d);
for (auto e : TMp)
if (e.first.first >= a && e.first.first <= c && e.first.second >= b && e.first.second <= d)
g = __gcd(g, e.second);
return g;
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19968 KB |
Output is correct |
2 |
Correct |
13 ms |
19968 KB |
Output is correct |
3 |
Correct |
12 ms |
19968 KB |
Output is correct |
4 |
Correct |
12 ms |
19968 KB |
Output is correct |
5 |
Correct |
12 ms |
19968 KB |
Output is correct |
6 |
Correct |
13 ms |
19968 KB |
Output is correct |
7 |
Correct |
12 ms |
19968 KB |
Output is correct |
8 |
Correct |
13 ms |
19968 KB |
Output is correct |
9 |
Correct |
12 ms |
19968 KB |
Output is correct |
10 |
Correct |
13 ms |
19968 KB |
Output is correct |
11 |
Correct |
13 ms |
19968 KB |
Output is correct |
12 |
Correct |
12 ms |
19968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19968 KB |
Output is correct |
2 |
Correct |
12 ms |
20096 KB |
Output is correct |
3 |
Correct |
13 ms |
19968 KB |
Output is correct |
4 |
Correct |
1226 ms |
25660 KB |
Output is correct |
5 |
Correct |
993 ms |
25956 KB |
Output is correct |
6 |
Runtime error |
69 ms |
40440 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19968 KB |
Output is correct |
2 |
Correct |
14 ms |
19968 KB |
Output is correct |
3 |
Correct |
13 ms |
19968 KB |
Output is correct |
4 |
Correct |
12 ms |
19968 KB |
Output is correct |
5 |
Correct |
13 ms |
19968 KB |
Output is correct |
6 |
Correct |
12 ms |
19968 KB |
Output is correct |
7 |
Correct |
14 ms |
19968 KB |
Output is correct |
8 |
Correct |
12 ms |
19968 KB |
Output is correct |
9 |
Correct |
14 ms |
19968 KB |
Output is correct |
10 |
Correct |
13 ms |
19968 KB |
Output is correct |
11 |
Correct |
12 ms |
19968 KB |
Output is correct |
12 |
Runtime error |
222 ms |
41976 KB |
Execution killed with signal 11 |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19968 KB |
Output is correct |
2 |
Correct |
12 ms |
19968 KB |
Output is correct |
3 |
Correct |
13 ms |
19968 KB |
Output is correct |
4 |
Correct |
13 ms |
19968 KB |
Output is correct |
5 |
Correct |
12 ms |
19968 KB |
Output is correct |
6 |
Correct |
12 ms |
19968 KB |
Output is correct |
7 |
Correct |
12 ms |
19968 KB |
Output is correct |
8 |
Correct |
12 ms |
19968 KB |
Output is correct |
9 |
Correct |
13 ms |
19968 KB |
Output is correct |
10 |
Correct |
13 ms |
19968 KB |
Output is correct |
11 |
Correct |
12 ms |
19968 KB |
Output is correct |
12 |
Correct |
1219 ms |
25592 KB |
Output is correct |
13 |
Correct |
970 ms |
25900 KB |
Output is correct |
14 |
Runtime error |
66 ms |
40440 KB |
Execution killed with signal 11 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19968 KB |
Output is correct |
2 |
Correct |
12 ms |
19968 KB |
Output is correct |
3 |
Correct |
13 ms |
19968 KB |
Output is correct |
4 |
Correct |
12 ms |
19968 KB |
Output is correct |
5 |
Correct |
12 ms |
19968 KB |
Output is correct |
6 |
Correct |
13 ms |
19968 KB |
Output is correct |
7 |
Correct |
12 ms |
19968 KB |
Output is correct |
8 |
Correct |
12 ms |
19968 KB |
Output is correct |
9 |
Correct |
13 ms |
19968 KB |
Output is correct |
10 |
Correct |
12 ms |
19968 KB |
Output is correct |
11 |
Correct |
12 ms |
19968 KB |
Output is correct |
12 |
Correct |
1222 ms |
25836 KB |
Output is correct |
13 |
Correct |
972 ms |
26104 KB |
Output is correct |
14 |
Runtime error |
63 ms |
40440 KB |
Execution killed with signal 11 |
15 |
Halted |
0 ms |
0 KB |
- |