oj.uz

Submission #914648

# Submission time Handle Problem Language Result Execution time Memory
914648 2024-01-22T13:09:01 Z anarch_y Regions (IOI09_regions) C++17
35 / 100
 8000 ms 68356 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
 
const int MX = 25001;
 
struct node{
    int val;
    int l, r;
};
 
struct pseg{
    static const int LIM = 4000000;
    node d[LIM];
    int nex = 0;
    vector<int> loc;
 
    int copy(int cur){
        int x = nex++;
        d[x] = d[cur];
        return x;
    }
 
    void push(int x){
        d[x].val = d[d[x].l].val + d[d[x].r].val;
    }
 
    int build(vector<int> &A, int L, int R){
        int cur = nex++;
        if(L == R){
            if(L < sz(A)) d[cur].val = A[L];
            return cur;
        }
        int M = (L+R)/2;
        d[cur].l = build(A, L, M);
        d[cur].r = build(A, M+1, R);
        push(cur);
        return cur;
    }
 
    void build(vector<int> &A){
        loc[0] = build(A, 0, MX-1);
    }
 
    int upd(int cur, int pos, int v, int L, int R){
        if(R < pos or pos < L) return cur;
        int x = copy(cur);
        if(pos <= L and R <= pos){
            d[x].val += v;
            return x;
        }
        int M = (L+R)/2;
        d[x].l = upd(d[x].l, pos, v, L, M);
        d[x].r = upd(d[x].r, pos, v, M+1, R);
        push(x);
        return x;
    }
 
    int upd(int cur, int id, int v){
        return upd(cur, id, v, 0, MX-1);
    }
 
    int query(int cur, int a, int b, int L, int R){  
        if(R < a or b < L) return 0;
        if(a <= L and R <= b) return d[cur].val;
        int M = (L+R)/2;
        int s1 = query(d[cur].l, a, b, L, M);
        int s2 = query(d[cur].r, a, b, M+1, R);
        return s1+s2;
    }
 
    int query(int cur, int a, int b){
        return query(cur, a, b, 0, MX-1);
    }
};
 
pseg P;
 
int query(int x, int y, int c){
    if(x == 0) return P.query(P.loc[y], c, c);
    return P.query(P.loc[y], c, c) - P.query(P.loc[x-1], c, c);
}
 
const int maxn = 200001;
vector<int> adj[maxn];
int sub[maxn], id[maxn], home[maxn];
vector<int> tour;
 
void dfs(int s, int p){
    sub[s] = 1;
    tour.pb(s);
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        sub[s] += sub[u];
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int N, R, Q; cin >> N >> R >> Q;
    vector<int> reg[R+1];
    int h; cin >> h;
    reg[h].pb(1); home[1] = h;
    for(int i=2; i<=N; i++){
        int p, r; cin >> p >> r;
        adj[i].pb(p); adj[p].pb(i);
        reg[r].pb(i);
        home[i] = r;
    }
    dfs(1, 0);
 
    vector<int> A(N, 0);
    for(int i=0; i<N; i++){
        id[tour[i]] = i;
        A[i] = home[tour[i]];
    }
 
    P.loc.resize(maxn);
    vector<int> t(MX, 0);
    t[A[0]] = 1;
    P.build(t);
    for(int i=1; i<N; i++){
        P.loc[i] = P.upd(P.loc[i-1], A[i], 1);
    }
 
    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        for(auto a: reg[r1]){
            ans += query(id[a], id[a]+sub[a]-1, r2);
        }
        cout << ans << "\n";
        cout.flush();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 4 ms 9568 KB Output is correct
4 Correct 4 ms 9560 KB Output is correct
5 Correct 8 ms 9600 KB Output is correct
6 Correct 12 ms 9672 KB Output is correct
7 Correct 22 ms 9648 KB Output is correct
8 Correct 27 ms 9684 KB Output is correct
9 Correct 40 ms 12196 KB Output is correct
10 Correct 82 ms 12156 KB Output is correct
11 Correct 153 ms 12400 KB Output is correct
12 Correct 185 ms 14996 KB Output is correct
13 Correct 242 ms 14924 KB Output is correct
14 Correct 516 ms 17244 KB Output is correct
15 Correct 666 ms 22296 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8005 ms 28220 KB Time limit exceeded
2 Execution timed out 8095 ms 27868 KB Time limit exceeded
3 Execution timed out 8029 ms 32220 KB Time limit exceeded
4 Correct 588 ms 17476 KB Output is correct
5 Correct 790 ms 19288 KB Output is correct
6 Correct 5141 ms 22920 KB Output is correct
7 Correct 6202 ms 25896 KB Output is correct
8 Execution timed out 8068 ms 37348 KB Time limit exceeded
9 Execution timed out 8074 ms 47012 KB Time limit exceeded
10 Execution timed out 8018 ms 54592 KB Time limit exceeded
11 Execution timed out 8039 ms 57044 KB Time limit exceeded
12 Execution timed out 8019 ms 53624 KB Time limit exceeded
13 Execution timed out 8013 ms 54820 KB Time limit exceeded
14 Execution timed out 8102 ms 56852 KB Time limit exceeded
15 Execution timed out 8077 ms 60776 KB Time limit exceeded
16 Execution timed out 8022 ms 68356 KB Time limit exceeded
17 Execution timed out 8087 ms 67000 KB Time limit exceeded