oj.uz

답안 #910612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910612 2024-01-18T06:17:48 Z anarch_y Regions (IOI09_regions) C++17
40 / 100
 8000 ms 68228 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 4 ms 9580 KB Output is correct
5 Correct 6 ms 9604 KB Output is correct
6 Correct 10 ms 9672 KB Output is correct
7 Correct 17 ms 9648 KB Output is correct
8 Correct 20 ms 9696 KB Output is correct
9 Correct 41 ms 12192 KB Output is correct
10 Correct 74 ms 12172 KB Output is correct
11 Correct 166 ms 12388 KB Output is correct
12 Correct 166 ms 14936 KB Output is correct
13 Correct 251 ms 14936 KB Output is correct
14 Correct 488 ms 17252 KB Output is correct
15 Correct 718 ms 22288 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8015 ms 28384 KB Time limit exceeded
2 Execution timed out 8066 ms 27772 KB Time limit exceeded
3 Execution timed out 8022 ms 32364 KB Time limit exceeded
4 Correct 412 ms 17496 KB Output is correct
5 Correct 446 ms 19296 KB Output is correct
6 Correct 2818 ms 22936 KB Output is correct
7 Correct 4774 ms 25900 KB Output is correct
8 Correct 7464 ms 37364 KB Output is correct
9 Execution timed out 8096 ms 47072 KB Time limit exceeded
10 Execution timed out 8074 ms 54628 KB Time limit exceeded
11 Execution timed out 8074 ms 57028 KB Time limit exceeded
12 Execution timed out 8042 ms 53700 KB Time limit exceeded
13 Execution timed out 8076 ms 54864 KB Time limit exceeded
14 Execution timed out 8036 ms 56844 KB Time limit exceeded
15 Execution timed out 8047 ms 61116 KB Time limit exceeded
16 Execution timed out 8041 ms 68228 KB Time limit exceeded
17 Execution timed out 8010 ms 66732 KB Time limit exceeded