| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403247 |
2021-05-13T00:18:51 Z |
rqi |
Regions (IOI09_regions) |
C++14 |
|
2890 ms |
38332 KB |
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
const int MOD = 1e9+7;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int mx = 200005;
const int BLOCK = 447;
const int REGION_mx = 25005;
//const int REGION_mx = 25;
int N, R, Q;
int par[mx];
vi children[mx];
int etind[mx]; //etind of an employee
pi etquery[mx];
int H[mx];
vi region_empls[REGION_mx]; // employees of a region
int sorted_region_ind[REGION_mx];
vpi region_queries[REGION_mx]; //count prefix up to f s times
vi region_updates[REGION_mx]; //update position +1
int pans[mx/BLOCK+5][REGION_mx];
int cans[mx/BLOCK+5][REGION_mx];
int cur_etind = 0;
void dfs(int node){
etind[node] = ++cur_etind;
etquery[node].f = cur_etind;
for(auto u: children[node]){
dfs(u);
}
etquery[node].s = cur_etind;
}
void genETinds(){
dfs(1);
assert(cur_etind == N);
}
int csum[mx];
void precomputeAnses(){
for(int r = 1; r <= R; r++){
if(sz(region_empls[r]) > BLOCK){
//do pans, cans[sorted_region_ind]
for(int i = N; i >= 0; i--){
csum[i] = 0;
}
for(auto &u: region_queries[r]){
csum[u.f]+=u.s;
}
for(int i = N; i >= 0; i--){
csum[i]+=csum[i+1];
}
for(int i = 1; i <= R; i++){
for(auto &u: region_updates[i]){
pans[sorted_region_ind[r]][i]+=csum[u];
#warning overflow
}
}
for(int i = 0; i <= N; i++){
csum[i] = 0;
}
for(auto &u: region_updates[r]){
csum[u]++;
}
for(int i = 1; i <= N; i++){
csum[i]+=csum[i-1];
}
for(int i = 1; i <= R; i++){
for(auto &u: region_queries[i]){
cans[sorted_region_ind[r]][i]+=csum[u.f]*u.s;
#warning overflow
}
}
}
}
}
int solveSmall(int r1, int r2){
// cout << "solving Small" << "\n";
// for(auto u: region_queries[r1]){
// cout << "region_queries: " << u.f << " " << u.s << "\n";
// }
// for(auto u: region_updates[r2]){
// cout << "region_updates: " << u << "\n";
// }
int query_ind = 0;
int update_ind = 0;
int res = 0;
int cur = 0;
while(true){
int query_num = MOD;
int update_num = MOD;
if(query_ind < sz(region_queries[r1])){
query_num = region_queries[r1][query_ind].f;
}
if(update_ind < sz(region_updates[r2])){
update_num = region_updates[r2][update_ind];
}
if(query_num == MOD && update_num == MOD) break;
//cout << "query, update ind: " << query_ind << " " << update_ind << "\n";
if(update_num <= query_num){
cur++;
//cout << "updated" << "\n";
update_ind++;
}
else{
res+=cur*region_queries[r1][query_ind].s;
//cout << "queried " << res << "\n";
query_ind++;
}
}
return res;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> N >> R >> Q;
for(int i = 1; i <= N; i++){
if(i != 1){
cin >> par[i];
children[par[i]].pb(i);
}
cin >> H[i];
region_empls[H[i]].pb(i);
}
genETinds();
// for(int i = 1; i <= N; i++){
// cout << "etind: " << i << " " << etind[i] << "\n";
// }
vpi sort_by_region_size;
for(int i = 1; i <= R; i++){
sort_by_region_size.pb(mp(sz(region_empls[i]), i));
}
sort(sort_by_region_size.rbegin(), sort_by_region_size.rend());
for(int i = 0; i < R; i++){
sorted_region_ind[sort_by_region_size[i].s] = i;
}
for(int i = 1; i <= N; i++){
region_queries[H[i]].pb(mp(etquery[i].f-1, -1));
region_queries[H[i]].pb(mp(etquery[i].s, 1));
region_updates[H[i]].pb(etind[i]);
}
for(int i = 1; i <= R; i++){
sort(all(region_queries[i]));
sort(all(region_updates[i]));
}
precomputeAnses();
for(int i = 1; i <= Q; i++){
int r1, r2;
cin >> r1 >> r2;
int ans = -1;
if(sz(region_empls[r1]) > BLOCK){
ans = pans[sorted_region_ind[r1]][r2];
}
else if(sz(region_empls[r2]) > BLOCK){
ans = cans[sorted_region_ind[r2]][r1];
}
else{
ans = solveSmall(r1, r2);
}
cout << ans << "\n";
cout.flush();
}
#warning int overflow
}
Compilation message
regions.cpp:78:22: warning: #warning overflow [-Wcpp]
78 | #warning overflow
| ^~~~~~~
regions.cpp:94:22: warning: #warning overflow [-Wcpp]
94 | #warning overflow
| ^~~~~~~
regions.cpp:196:6: warning: #warning int overflow [-Wcpp]
196 | #warning int overflow
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6796 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6728 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6728 KB |
Output is correct |
| 5 |
Correct |
14 ms |
6856 KB |
Output is correct |
| 6 |
Correct |
30 ms |
6856 KB |
Output is correct |
| 7 |
Correct |
44 ms |
6856 KB |
Output is correct |
| 8 |
Correct |
36 ms |
6984 KB |
Output is correct |
| 9 |
Correct |
55 ms |
7432 KB |
Output is correct |
| 10 |
Correct |
107 ms |
7624 KB |
Output is correct |
| 11 |
Correct |
114 ms |
8140 KB |
Output is correct |
| 12 |
Correct |
136 ms |
8836 KB |
Output is correct |
| 13 |
Correct |
187 ms |
8648 KB |
Output is correct |
| 14 |
Correct |
222 ms |
9664 KB |
Output is correct |
| 15 |
Correct |
218 ms |
12412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
916 ms |
14048 KB |
Output is correct |
| 2 |
Correct |
1062 ms |
13096 KB |
Output is correct |
| 3 |
Correct |
1704 ms |
16272 KB |
Output is correct |
| 4 |
Correct |
285 ms |
9664 KB |
Output is correct |
| 5 |
Correct |
407 ms |
11208 KB |
Output is correct |
| 6 |
Correct |
707 ms |
15296 KB |
Output is correct |
| 7 |
Correct |
945 ms |
14784 KB |
Output is correct |
| 8 |
Correct |
1002 ms |
27748 KB |
Output is correct |
| 9 |
Correct |
1594 ms |
21776 KB |
Output is correct |
| 10 |
Correct |
2468 ms |
38332 KB |
Output is correct |
| 11 |
Correct |
2890 ms |
22720 KB |
Output is correct |
| 12 |
Correct |
1046 ms |
24248 KB |
Output is correct |
| 13 |
Correct |
1423 ms |
24396 KB |
Output is correct |
| 14 |
Correct |
1592 ms |
28004 KB |
Output is correct |
| 15 |
Correct |
2311 ms |
29236 KB |
Output is correct |
| 16 |
Correct |
2421 ms |
33980 KB |
Output is correct |
| 17 |
Correct |
2260 ms |
36696 KB |
Output is correct |
