oj.uz

Submission #1092677

# Submission time Handle Problem Language Result Execution time Memory
1092677 2024-09-24T18:07:59 Z vjudge1 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
// #define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(ll &a, ll b) { if(b<a){a=b;return 1;}return 0; }
bool cmax(ll &a, ll b) { if(b>a){a=b;return 1;}return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }

struct SegTree{
    SegTree *left, *right;
    int l,r,sum=0;
    SegTree(){}
    SegTree(int l, int r):l(l),r(r){}
    void build(){
        if(l==r)sum=0;
        else{
            int mid = (l+r)/2;
            left = new SegTree(l, mid);
            right = new SegTree(mid+1, r);
            left->build();right->build();
        }
    }
    SegTree *update(int i, int v){
        if(r<i || l>i)return this;
        SegTree *t = new SegTree(l, r);
        if(l==r)t->sum=sum+v;
        else{
            t->left=left->update(i, v);
            t->right=right->update(i,v);
            t->sum=t->left->sum+t->right->sum;
        }
        return t;
    }
    int query(int i, int j){
        if(l>j||r<i)return 0;
        if(l>=i&&r<=j)return sum;
        return right->query(i, j)+left->query(i,j);
    }
};
const int N = 2e5 + 7;
int pa[N], h[N], el[N], tin[N], tout[N], timer, n, r, Q;
vi graph[N];
map<int, int> rd[N];
SegTree *st[N];
void test_case() {
    cin >> n >> r >> Q;
    vector<vi> ord(r+1); 
    cin >> h[1];
    fore (i, 2, n+1) {
        cin >> pa[i];
        graph[pa[i]].pb(i);
        cin >> h[i];
    }
    fore (i, 1, n+1) ord[h[i]].pb(i);
    if (r <= 500) {
        vector<vi> dp(501, vi(501, 0));
        function<void(int)> dfs = [&](int u) {
            rd[u][h[u]]++;
            for(int v: graph[u]) {
                dfs(v);
                if(sz(rd[v]) > sz(rd[u])) swap(rd[u], rd[v]);
                for (auto [k, vl]: rd[v]) {
                    rd[u][k] += vl;
                }
            }
            for (auto [k, vl]: rd[u]) dp[h[u]][k] += vl;
        };
        dfs(1);
        while (Q--) {
            int r1, r2;
            cin >> r1 >> r2;
            cout << dp[r1][r2] << endl;
        }
        return;
    }
     int mx = 0;
    // fore (i, 1, r+1) mx = max(mx, sz(ord[i])); 
    // assert(mx <= 500);
    timer = 1;
    function<void(int)> dfs = [&](int u) {
        el[timer]=u;
        tin[u] = timer++;
        for(int v: graph[u]) dfs(v);
        tout[u] = timer-1;
    };
    dfs(1);
    st[0] = new SegTree(1, r);
    st[0]->build();
    fore (i, 1, n+1) st[i] = st[i-1]->update(h[el[i]], +1);
    while (Q--) {
        int r1, r2;
        cin >> r1 >> r2;
        int ans = 0;
        for(int e1: ord[r1]) {
            ans += st[tout[e1]]->query(r2, r2) - st[tin[e1]-1]->query(r2, r2);
        }
        cout << ans << endl;
    }
} 

int main() {
    int tt = 1;
    // cin >> tt;
    while(tt--) test_case();
}

Compilation message

regions.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
regions.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
regions.cpp: In function 'void test_case()':
regions.cpp:110:10: warning: unused variable 'mx' [-Wunused-variable]
  110 |      int mx = 0;
      |          ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15448 KB Output is correct
2 Correct 6 ms 15448 KB Output is correct
3 Correct 6 ms 15448 KB Output is correct
4 Correct 7 ms 15448 KB Output is correct
5 Correct 10 ms 15412 KB Output is correct
6 Correct 18 ms 15704 KB Output is correct
7 Correct 21 ms 15700 KB Output is correct
8 Correct 18 ms 15704 KB Output is correct
9 Correct 50 ms 16728 KB Output is correct
10 Correct 61 ms 17240 KB Output is correct
11 Correct 78 ms 17752 KB Output is correct
12 Correct 147 ms 18512 KB Output is correct
13 Correct 100 ms 19500 KB Output is correct
14 Correct 115 ms 20312 KB Output is correct
15 Correct 271 ms 25944 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 25936 KB Output is correct
2 Correct 738 ms 26408 KB Output is correct
3 Correct 1159 ms 30224 KB Output is correct
4 Correct 666 ms 35152 KB Output is correct
5 Correct 696 ms 43596 KB Output is correct
6 Correct 4482 ms 52560 KB Output is correct
7 Execution timed out 8093 ms 67664 KB Time limit exceeded
8 Execution timed out 8050 ms 97192 KB Time limit exceeded
9 Runtime error 183 ms 131072 KB Execution killed with signal 9
10 Runtime error 164 ms 131072 KB Execution killed with signal 9
11 Runtime error 187 ms 131072 KB Execution killed with signal 9
12 Runtime error 191 ms 131072 KB Execution killed with signal 9
13 Runtime error 180 ms 131072 KB Execution killed with signal 9
14 Runtime error 198 ms 131072 KB Execution killed with signal 9
15 Runtime error 182 ms 131072 KB Execution killed with signal 9
16 Runtime error 187 ms 131072 KB Execution killed with signal 9
17 Runtime error 182 ms 131072 KB Execution killed with signal 9