| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 281813 |
2020-08-23T13:59:59 Z |
Saboon |
Game (IOI13_game) |
C++14 |
|
1 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SQ = 150;
ll gcd2(ll X, ll Y){
ll tmp;
while (X != Y && Y != 0){
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int seg[SQ][8*SQ];
int get(int id, int L, int R, int l, int r, int block){
if (r <= L or R <= l)
return 0;
if (l <= L and R <= r)
return seg[block][id];
int mid = (L + R) >> 1;
return gcd2(get(2*id+0, L, mid, l, r, block),
get(2*id+1, mid, R, l, r, block));
}
void change(int id, int L, int R, int idx, ll K, int block){
if (idx < L or R <= idx)
return;
if (L + 1 == R){
seg[block][id] = K;
return;
}
int mid = (L + R) >> 1;
change(2*id+0, L, mid, idx, K, block);
change(2*id+1, mid, R, idx, K, block);
seg[block][id] = gcd2(seg[block][2*id+0], seg[block][2*id+1]);
}
int numBlock;
vector<pair<pair<int,int>,ll>> a[SQ];
map<pair<int,int>, ll> mp;
vector<pair<int,ll>> b[SQ];
void changeblock(int block){
for (int i = 0; i < 4*305; i++)
seg[block][i] = 0;
b[block].clear();
for (auto it : a[block])
b[block].push_back({it.first.second,it.second});
sort(b[block].begin(), b[block].end());
for (int i = 0; i < b[block].size(); i++)
change(1, 0, b[block].size(), i, b[block][i].second, block);
}
void init(int R, int C){
for (int i = 0; i < SQ; i++)
a[i].clear();
int n = mp.size();
numBlock = max((n+SQ-1)/SQ,1);
int idx = -1;
for (auto it : mp){
idx ++;
a[idx/SQ].push_back(it);
}
for (int i = 0; i < numBlock; i++)
changeblock(i);
}
void update(int P, int Q, ll K){
mp[{P,Q}] = K;
int block = numBlock-1;
for (int i = 1; i < numBlock; i++)
if (P <= a[i][0].first.first)
block = i-1;
a[block].push_back({{P,Q},K});
if (a[block].size() == 2*SQ)
init(0,0);
else
changeblock(block);
}
ll calculate(int P, int Q, int U, int V){
if (P > U)
swap(P, U);
if (Q > V)
swap(Q, V);
ll answer = 0;
for (int i = 0; i < numBlock; i++){
if (a[i].empty())
continue;
if (a[i][0].first.first > U)
break;
if (a[i].back().first.first < P)
continue;
if (a[i][0].first.first >= P and a[i].back().first.first <= U){
int lo = lower_bound(b[i].begin(), b[i].end(), make_pair(Q,-1LL)) - b[i].begin();
int hi = lower_bound(b[i].begin(), b[i].end(), make_pair(U+1, -1LL)) - b[i].begin();
answer = gcd2(answer, get(1, 0, b[i].size(), lo, hi, i));
continue;
}
for (auto it : a[i]){
int p = it.first.first, q = it.first.second;
ll x = it.second;
if (P <= p and p <= U and Q <= q and q <= V)
answer = gcd2(answer, x);
}
}
return answer;
}
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;
| ^~~
game.cpp: In function 'void changeblock(int)':
game.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < b[block].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
game.cpp:49:17: warning: iteration 1200 invokes undefined behavior [-Waggressive-loop-optimizations]
49 | seg[block][i] = 0;
| ~~~~~~~~~~~~~~^~~
game.cpp:48:20: note: within this loop
48 | for (int i = 0; i < 4*305; i++)
| ~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
