oj.uz

Submission #863017

# Submission time Handle Problem Language Result Execution time Memory
863017 2023-10-19T13:16:23 Z 8pete8 Osumnjičeni (COCI21_osumnjiceni) C++14
110 / 110
 925 ms 98336 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,pii>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mod=9901,mxn=4*1e5+5,inf=1e18,lg=25,minf=-1e18;
int seg[4*mxn+10],add[4*mxn+10],nxt[mxn+10],up[mxn+10][lg+5];
pii pos[mxn+10];
vector<int>v;
vector<pii>id;
void init(){for(int i=0;i<=4*mxn+5;i++)seg[i]=inf,add[i]=inf;}
void push(int pos,int l,int r){
    seg[pos]=min(seg[pos],add[pos]);
    if(l!=r){
        add[pos*2]=min(add[pos],add[pos*2+1]);
        add[pos*2+1]=min(add[pos],add[pos*2+1]);
    }
    add[pos]=inf;
}
int qry(int l,int r,int ql,int qr,int pos){
    push(pos,l,r);
    int mid=l+(r-l)/2;
    if(l>qr||r<ql)return inf; 
    if(ql<=l&&r<=qr)return seg[pos];
    return min(qry(l,mid,ql,qr,pos*2),qry(mid+1,r,ql,qr,pos*2+1));
}
void update(int l,int r,int ql,int qr,int pos,int val){
    push(pos,l,r);
    int mid=l+(r-l)/2;
    if(l>qr||r<ql)return;
    if(ql<=l&&r<=qr){
        add[pos]=min(add[pos],val);
        push(pos,l,r);
        return;
    }
    update(l,mid,ql,qr,pos*2,val);
    update(mid+1,r,ql,qr,pos*2+1,val);
    seg[pos]=min(seg[pos*2],seg[pos*2+1]);
}
int32_t main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        id.pb({a,b});
        v.pb(a);
        v.pb(b);
    }
    sort(all(v));
    for(int i=0;i<n;i++){
        pos[i].f=lb(all(v),id[i].f)-v.begin();
        pos[i].s=lb(all(v),id[i].s)-v.begin();
    }
    init();
    nxt[n]=n;
    for(int i=n-1;i>=0;i--){
        nxt[i]=qry(0,mxn+5,pos[i].f,pos[i].s,1);
        update(0,mxn+5,pos[i].f,pos[i].s,1,i);
        nxt[i]=min(nxt[i],nxt[i+1]);
        up[i][0]=nxt[i];
    }
    for(int i=1;i<=lg;i++)for(int j=0;j<n;j++)if(up[j][i-1]!=0)up[j][i]=up[up[j][i-1]][i-1];
    int a,b,ans,m;cin>>m;
    while(m--){
        ans=0;
        cin>>a>>b;
        --a,--b;
        for(int i=lg;i>=0;i--)if(up[a][i]-1<b&&up[a][i])a=up[a][i],ans+=(1ll<<i);
        cout<<ans+1<<'\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 88996 KB Output is correct
2 Correct 428 ms 92320 KB Output is correct
3 Correct 418 ms 92300 KB Output is correct
4 Correct 465 ms 92056 KB Output is correct
5 Correct 471 ms 94316 KB Output is correct
6 Correct 209 ms 90724 KB Output is correct
7 Correct 215 ms 92060 KB Output is correct
8 Correct 223 ms 92088 KB Output is correct
9 Correct 224 ms 92304 KB Output is correct
10 Correct 244 ms 90972 KB Output is correct
11 Correct 324 ms 93348 KB Output is correct
12 Correct 302 ms 89764 KB Output is correct
13 Correct 343 ms 89504 KB Output is correct
14 Correct 323 ms 93784 KB Output is correct
15 Correct 313 ms 90748 KB Output is correct
16 Correct 4 ms 30044 KB Output is correct
17 Correct 250 ms 94676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 32604 KB Output is correct
2 Correct 20 ms 32348 KB Output is correct
3 Correct 20 ms 32356 KB Output is correct
4 Correct 20 ms 32348 KB Output is correct
5 Correct 21 ms 32580 KB Output is correct
6 Correct 17 ms 32600 KB Output is correct
7 Correct 24 ms 32348 KB Output is correct
8 Correct 19 ms 32348 KB Output is correct
9 Correct 18 ms 32348 KB Output is correct
10 Correct 17 ms 32344 KB Output is correct
11 Correct 18 ms 32580 KB Output is correct
12 Correct 18 ms 32348 KB Output is correct
13 Correct 18 ms 32344 KB Output is correct
14 Correct 18 ms 32348 KB Output is correct
15 Correct 18 ms 32588 KB Output is correct
16 Correct 5 ms 30240 KB Output is correct
17 Correct 17 ms 32596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 32604 KB Output is correct
2 Correct 20 ms 32348 KB Output is correct
3 Correct 20 ms 32356 KB Output is correct
4 Correct 20 ms 32348 KB Output is correct
5 Correct 21 ms 32580 KB Output is correct
6 Correct 17 ms 32600 KB Output is correct
7 Correct 24 ms 32348 KB Output is correct
8 Correct 19 ms 32348 KB Output is correct
9 Correct 18 ms 32348 KB Output is correct
10 Correct 17 ms 32344 KB Output is correct
11 Correct 18 ms 32580 KB Output is correct
12 Correct 18 ms 32348 KB Output is correct
13 Correct 18 ms 32344 KB Output is correct
14 Correct 18 ms 32348 KB Output is correct
15 Correct 18 ms 32588 KB Output is correct
16 Correct 5 ms 30240 KB Output is correct
17 Correct 17 ms 32596 KB Output is correct
18 Correct 334 ms 33240 KB Output is correct
19 Correct 333 ms 33244 KB Output is correct
20 Correct 334 ms 33620 KB Output is correct
21 Correct 317 ms 33448 KB Output is correct
22 Correct 320 ms 33364 KB Output is correct
23 Correct 300 ms 33364 KB Output is correct
24 Correct 321 ms 33364 KB Output is correct
25 Correct 326 ms 33540 KB Output is correct
26 Correct 358 ms 33164 KB Output is correct
27 Correct 300 ms 33108 KB Output is correct
28 Correct 326 ms 33088 KB Output is correct
29 Correct 311 ms 32852 KB Output is correct
30 Correct 316 ms 33164 KB Output is correct
31 Correct 310 ms 32852 KB Output is correct
32 Correct 323 ms 33104 KB Output is correct
33 Correct 5 ms 30040 KB Output is correct
34 Correct 306 ms 33368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 90628 KB Output is correct
2 Correct 440 ms 94372 KB Output is correct
3 Correct 429 ms 89512 KB Output is correct
4 Correct 452 ms 89940 KB Output is correct
5 Correct 407 ms 92836 KB Output is correct
6 Correct 210 ms 90064 KB Output is correct
7 Correct 208 ms 88996 KB Output is correct
8 Correct 210 ms 89456 KB Output is correct
9 Correct 212 ms 89000 KB Output is correct
10 Correct 232 ms 94200 KB Output is correct
11 Correct 304 ms 88336 KB Output is correct
12 Correct 326 ms 93756 KB Output is correct
13 Correct 309 ms 89240 KB Output is correct
14 Correct 301 ms 91472 KB Output is correct
15 Correct 327 ms 93348 KB Output is correct
16 Correct 4 ms 30040 KB Output is correct
17 Correct 217 ms 91048 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 88996 KB Output is correct
2 Correct 428 ms 92320 KB Output is correct
3 Correct 418 ms 92300 KB Output is correct
4 Correct 465 ms 92056 KB Output is correct
5 Correct 471 ms 94316 KB Output is correct
6 Correct 209 ms 90724 KB Output is correct
7 Correct 215 ms 92060 KB Output is correct
8 Correct 223 ms 92088 KB Output is correct
9 Correct 224 ms 92304 KB Output is correct
10 Correct 244 ms 90972 KB Output is correct
11 Correct 324 ms 93348 KB Output is correct
12 Correct 302 ms 89764 KB Output is correct
13 Correct 343 ms 89504 KB Output is correct
14 Correct 323 ms 93784 KB Output is correct
15 Correct 313 ms 90748 KB Output is correct
16 Correct 4 ms 30044 KB Output is correct
17 Correct 250 ms 94676 KB Output is correct
18 Correct 21 ms 32604 KB Output is correct
19 Correct 20 ms 32348 KB Output is correct
20 Correct 20 ms 32356 KB Output is correct
21 Correct 20 ms 32348 KB Output is correct
22 Correct 21 ms 32580 KB Output is correct
23 Correct 17 ms 32600 KB Output is correct
24 Correct 24 ms 32348 KB Output is correct
25 Correct 19 ms 32348 KB Output is correct
26 Correct 18 ms 32348 KB Output is correct
27 Correct 17 ms 32344 KB Output is correct
28 Correct 18 ms 32580 KB Output is correct
29 Correct 18 ms 32348 KB Output is correct
30 Correct 18 ms 32344 KB Output is correct
31 Correct 18 ms 32348 KB Output is correct
32 Correct 18 ms 32588 KB Output is correct
33 Correct 5 ms 30240 KB Output is correct
34 Correct 17 ms 32596 KB Output is correct
35 Correct 334 ms 33240 KB Output is correct
36 Correct 333 ms 33244 KB Output is correct
37 Correct 334 ms 33620 KB Output is correct
38 Correct 317 ms 33448 KB Output is correct
39 Correct 320 ms 33364 KB Output is correct
40 Correct 300 ms 33364 KB Output is correct
41 Correct 321 ms 33364 KB Output is correct
42 Correct 326 ms 33540 KB Output is correct
43 Correct 358 ms 33164 KB Output is correct
44 Correct 300 ms 33108 KB Output is correct
45 Correct 326 ms 33088 KB Output is correct
46 Correct 311 ms 32852 KB Output is correct
47 Correct 316 ms 33164 KB Output is correct
48 Correct 310 ms 32852 KB Output is correct
49 Correct 323 ms 33104 KB Output is correct
50 Correct 5 ms 30040 KB Output is correct
51 Correct 306 ms 33368 KB Output is correct
52 Correct 457 ms 90628 KB Output is correct
53 Correct 440 ms 94372 KB Output is correct
54 Correct 429 ms 89512 KB Output is correct
55 Correct 452 ms 89940 KB Output is correct
56 Correct 407 ms 92836 KB Output is correct
57 Correct 210 ms 90064 KB Output is correct
58 Correct 208 ms 88996 KB Output is correct
59 Correct 210 ms 89456 KB Output is correct
60 Correct 212 ms 89000 KB Output is correct
61 Correct 232 ms 94200 KB Output is correct
62 Correct 304 ms 88336 KB Output is correct
63 Correct 326 ms 93756 KB Output is correct
64 Correct 309 ms 89240 KB Output is correct
65 Correct 301 ms 91472 KB Output is correct
66 Correct 327 ms 93348 KB Output is correct
67 Correct 4 ms 30040 KB Output is correct
68 Correct 217 ms 91048 KB Output is correct
69 Correct 847 ms 95900 KB Output is correct
70 Correct 861 ms 98172 KB Output is correct
71 Correct 818 ms 92888 KB Output is correct
72 Correct 925 ms 94844 KB Output is correct
73 Correct 843 ms 94608 KB Output is correct
74 Correct 690 ms 98336 KB Output is correct
75 Correct 646 ms 93096 KB Output is correct
76 Correct 639 ms 97956 KB Output is correct
77 Correct 584 ms 93572 KB Output is correct
78 Correct 712 ms 95620 KB Output is correct
79 Correct 670 ms 96356 KB Output is correct
80 Correct 616 ms 92672 KB Output is correct
81 Correct 618 ms 92300 KB Output is correct
82 Correct 640 ms 97184 KB Output is correct
83 Correct 620 ms 94644 KB Output is correct
84 Correct 4 ms 30044 KB Output is correct
85 Correct 547 ms 92700 KB Output is correct