oj.uz

Submission #490586

# Submission time Handle Problem Language Result Execution time Memory
490586 2021-11-28T07:10:36 Z CyberSleeper Regions (IOI09_regions) C++14
25 / 100
 8000 ms 50836 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ld          long double
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define ar3         array<int, 3>
#define nl          endl
#define tb          '\t'
#define sp          ' '
using namespace std;

const int MX=200005, MOD=1e9+7, BLOCK=500, INF=1e9+7, INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

int N, R, Q, op[MX], ed[MX], reg[MX];
vector<int> adj[MX], euler;
vector<pii> rakyat[25005];

void DFS(int p, int x){
    op[x]=euler.size();
    euler.pb(reg[x]);
    for(auto i:adj[x]){
        DFS(x, i);
    }
    ed[x]=euler.size()-1;
}

int main(){
    //fastio;
    cin >> N >> R >> Q >> reg[1];
    for(int i=2, P; i<=N; i++){
        cin >> P >> reg[i];
        adj[P].pb(i);
    }
    DFS(0, 1);
    for(int i=1; i<=N; i++){
        int tmp=reg[i];
        rakyat[tmp].pb({op[i], ed[i]});
    }
    for(int i=0; i<=R; i++)
        sort(rakyat[i].begin(), rakyat[i].end());
    map<pii, int> prec;
    for(int i=1; i<=R; i++){
        if(rakyat[i].size()>BLOCK){
            int cnt=0, idx=0;
            vector<int> sweep(N+1, 0);
            for(auto j:rakyat[i]){
                sweep[j.fi]++;
                sweep[j.se+1]--;
            }
            for(int j=0; j<N; j++){
                cnt+=sweep[j];
                prec[{i, euler[j]}]+=cnt;
            }
        }
    }
    for(int u, v; Q--;){
        cin >> u >> v;
        if(rakyat[u].size()>BLOCK)
            cout << prec[{u, v}] << nl;
        else{
            int ans=0;
            for(auto i:rakyat[v]){
                int add=upper_bound(rakyat[u].begin(), rakyat[u].end(), mp(i.fi, INF))-rakyat[u].begin(), dic;
                vector<int> tmped;
                for(auto i:rakyat[u])
                    tmped.pb(i.se);
                sort(tmped.begin(), tmped.end());
                int le=0, ri=tmped.size()-1, mi;
                while(le<=ri){
                    mi=(le+ri)/2;
                    if(tmped[mi]>=i.fi){
                        ri=mi-1;
                        dic=mi;
                    }else{
                        le=mi+1;
                    }
                }
                dic=ri+1;
                ans+=add-dic;
            }
            cout << ans << nl;
        }
    }
}

Compilation message

regions.cpp:18:64: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int MX=200005, MOD=1e9+7, BLOCK=500, INF=1e9+7, INFF=1e18+7;
      |                                                            ~~~~^~
regions.cpp: In function 'int main()':
regions.cpp:51:24: warning: unused variable 'idx' [-Wunused-variable]
   51 |             int cnt=0, idx=0;
      |                        ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5576 KB Output is correct
2 Correct 3 ms 5576 KB Output is correct
3 Correct 4 ms 5576 KB Output is correct
4 Correct 13 ms 5576 KB Output is correct
5 Correct 15 ms 5600 KB Output is correct
6 Correct 20 ms 5576 KB Output is correct
7 Correct 39 ms 5576 KB Output is correct
8 Correct 45 ms 5704 KB Output is correct
9 Correct 81 ms 6088 KB Output is correct
10 Correct 136 ms 6088 KB Output is correct
11 Correct 470 ms 6472 KB Output is correct
12 Correct 463 ms 7000 KB Output is correct
13 Correct 888 ms 6720 KB Output is correct
14 Correct 4126 ms 7232 KB Output is correct
15 Correct 4943 ms 9860 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8099 ms 10944 KB Time limit exceeded
2 Execution timed out 8048 ms 9736 KB Time limit exceeded
3 Execution timed out 8085 ms 12900 KB Time limit exceeded
4 Correct 898 ms 7240 KB Output is correct
5 Correct 963 ms 8896 KB Output is correct
6 Execution timed out 8045 ms 8516 KB Time limit exceeded
7 Execution timed out 8069 ms 9688 KB Time limit exceeded
8 Execution timed out 8026 ms 14576 KB Time limit exceeded
9 Execution timed out 8061 ms 15448 KB Time limit exceeded
10 Execution timed out 8036 ms 19792 KB Time limit exceeded
11 Execution timed out 8010 ms 15000 KB Time limit exceeded
12 Execution timed out 8029 ms 19156 KB Time limit exceeded
13 Execution timed out 8047 ms 19276 KB Time limit exceeded
14 Execution timed out 8068 ms 40984 KB Time limit exceeded
15 Execution timed out 8006 ms 24352 KB Time limit exceeded
16 Execution timed out 8005 ms 29812 KB Time limit exceeded
17 Execution timed out 8058 ms 50836 KB Time limit exceeded