| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 67414 | 2018-08-14T08:49:21 Z | Crown | Regions (IOI09_regions) | C++14 | 1878 ms | 86480 KB |
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
#define lim 316
const int maxn = 2e5+5;
const int maxr = 3e4+5;
vector<int> adj[maxn];
int re[maxn];
int num[maxn];
int cnt[maxn];
int cur = 0;
int n, r, q;
vector<int> regions[maxn];
vector<int> blocks[maxn];
vector< ii > res[maxn];
void dfs(int u, int p)
{
cur++;
num[u] = cur;
cnt[u] = 1;
for(auto v : adj[u])
{
if(v == p) continue;
dfs(v, u);
cnt[u] += cnt[v];
}
}
bool cmp(int a, int b)
{
if(abs(a) != abs(b)) return abs(a)< abs(b);
return a< b;
}
map<ii, ll> cache;
int main()
{
scanf("%d %d %d", &n, &r, &q);
scanf("%d", re+1);
for(int i = 2; i<= n; i++)
{
int x;
scanf("%d %d", &x, &re[i]);
adj[x].pb(i);
}
dfs(1, 0);
for(int i = 1; i<= n; i++)
{
regions[re[i]].pb(num[i]);
blocks[re[i]].pb(num[i]);
blocks[re[i]].pb(-num[i]-cnt[i]);
}
for(int i = 1; i<= r; i++)
{
sort(regions[i].begin(), regions[i].end());
sort(blocks[i].begin(), blocks[i].end(), cmp);
vector< ii > tmp;
for(int j = 0; j< (int) blocks[i].size(); j++)
{
if(tmp.empty() || abs(blocks[i][j]) != tmp.back().X)
{
tmp.pb(ii(abs(blocks[i][j]), blocks[i][j]>0?1:-1));
}
else
{
tmp.back().Y += (blocks[i][j]>0?1:-1);
}
}
res[i].pb(tmp[0]);
for(int j = 1; j< (int) tmp.size(); j++)
{
res[i].pb(ii(tmp[j].X, res[i].back().Y+tmp[j].Y));
}
}
while(q--)
{
int r1, r2; scanf("%d %d", &r1, &r2);
if(cache.find(ii(r1, r2)) != cache.end())
{
printf("%lld\n", cache[ii(r1, r2)]);
fflush(stdout);
continue;
}
ll ret = 0;
if(r1>= lim || r2>= lim)
{
assert(0);
if(r1> r2)
{
for(auto x : regions[r2])
{
int ind = upper_bound(res[r1].begin(), res[r1].end(), ii(x, 1e9))-res[r1].begin()-1;
if(ind< 0) continue;
ret += res[r1][ind].Y;
}
}
else
{
for(int i = 1; i< (int) res[r1].size(); i++)
{
int lb = res[r1][i-1].X;
int rb = res[r1][i].X-1;
int cnt = res[r1][i-1].Y;
int cnt2 = lower_bound(regions[r2].begin(), regions[r2].end(), rb)-lower_bound(regions[r2].begin(), regions[r2].end(), lb-1);
ret += 1LL*cnt*cnt2;
}
}
}
else
{
int pt = 0;
for(auto x : regions[r2])
{
while(pt< (int) res[r1].size() && res[r1][pt].X<= x) pt++;
if(pt) ret += res[r1][pt-1].Y;
}
}
cache[ii(r1, r2)] = ret;
printf("%lld\n", ret);
fflush(stdout);
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 44 ms | 38008 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 54 ms | 38164 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 51 ms | 38260 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Incorrect | 29 ms | 38308 KB | Unexpected end of file - int32 expected |
| 5 | Incorrect | 36 ms | 38432 KB | Unexpected end of file - int32 expected |
| 6 | Runtime error | 49 ms | 38576 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Incorrect | 55 ms | 38752 KB | Unexpected end of file - int32 expected |
| 8 | Incorrect | 55 ms | 38928 KB | Unexpected end of file - int32 expected |
| 9 | Incorrect | 72 ms | 39472 KB | Unexpected end of file - int32 expected |
| 10 | Runtime error | 48 ms | 40204 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Incorrect | 178 ms | 41108 KB | Expected integer, but "prog1:" found |
| 12 | Runtime error | 81 ms | 42444 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 63 ms | 42560 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 | Incorrect | 241 ms | 43648 KB | Expected integer, but "prog1:" found |
| 15 | Incorrect | 209 ms | 46892 KB | Expected integer, but "prog1:" found |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 953 ms | 48720 KB | Expected integer, but "prog1:" found |
| 2 | Incorrect | 1209 ms | 48720 KB | Expected integer, but "prog1:" found |
| 3 | Incorrect | 1878 ms | 53252 KB | Expected integer, but "prog1:" found |
| 4 | Runtime error | 70 ms | 53252 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 68 ms | 53252 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 84 ms | 53252 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 82 ms | 53252 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 141 ms | 62672 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 161 ms | 62672 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 168 ms | 71424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Runtime error | 212 ms | 71424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 | Runtime error | 216 ms | 71424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 178 ms | 71424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 | Runtime error | 221 ms | 71424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 | Runtime error | 218 ms | 76152 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 | Runtime error | 218 ms | 86480 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 | Runtime error | 194 ms | 86480 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |