oj.uz

Submission #751396

# Submission time Handle Problem Language Result Execution time Memory
751396 2023-05-31T13:48:24 Z bgnbvnbv Osumnjičeni (COCI21_osumnjiceni) C++14
110 / 110
 729 ms 101548 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct Tinter
{
    ll l,r,id;
    bool operator<(const Tinter&o)
    {
        return l<o.l;
    }
}e[maxN];
ll lazy[8*maxN],st[8*maxN];
void down(ll id)
{
    ll &x=lazy[id];
    if(x!=-1)
    {
        st[id*2]=x;
        lazy[id*2]=x;
        st[id*2+1]=x;
        lazy[id*2+1]=x;
        x=-1;
    }
}
ll n;
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=2*n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]=val;
        lazy[id]=val;
        return;
    }
    ll mid=l+r>>1;
    down(id);
    update(i,j,val,id*2,l,mid);
    update(i,j,val,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=2*n)
{
    if(j<l||r<i) return n+1;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    down(id);
    return min(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
ll r[maxN];
ll mn[maxN][19],nxt[maxN][19];
int log(ll x)
{
    return 64 - __builtin_clzll(x) - 1;
}
ll g(ll i,ll j)
{
    ll k=j-i+1;
    k=log(k);
    return min(mn[i][k],mn[j-(1<<k)+1][k]);
}
void solve()
{
    vector<ll>vec;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> e[i].l >> e[i].r;
        vec.pb(e[i].l);
        vec.pb(e[i].r);
        e[i].id=i;
        r[i]=n+1;
    }
    sort(vec.begin(),vec.end());
    for(int i=1;i<=n;i++)
    {
        e[i].l=lower_bound(vec.begin(),vec.end(),e[i].l)-vec.begin()+1;
        e[i].r=lower_bound(vec.begin(),vec.end(),e[i].r)-vec.begin()+1;
    }
    fill(st,st+8*maxN,n+1);
    fill(lazy,lazy+8*maxN,-1);
    for(int i=n;i>=1;i--)
    {
        r[i]=min(r[i],get(e[i].l,e[i].r));
        update(e[i].l,e[i].r,i);
        mn[i][0]=r[i];
        //cout << r[i]<<' ';
    }
    for(int j=1;j<=18;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i+(1<<j)-1>n) break;
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        ll low=i,high=n;
        while(low<=high)
        {
            ll mid=low+high>>1;
            if(g(i,mid)>mid) low=mid+1;
            else high=mid-1;
        }
        nxt[i][0]=low;
    }
    //cout << '\n';
    nxt[n+1][0]=n+1;
    for(int j=1;j<=18;j++)
    {
        for(int i=1;i<=n+1;i++)
        {
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        }
    }
    ll q;
    cin >> q;
    while(q--)
    {
        ll a,b;
        cin >> a >> b;
        ll ans=1;
        for(int j=18;j>=0;j--)
        {
            if(nxt[a][j]<=b)
            {
                a=nxt[a][j];
                ans+=1<<j;
            }
        }
        cout << ans<<'\n';

    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

Main.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
Main.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'void solve()':
Main.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |             ll mid=low+high>>1;
      |                    ~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 94996 KB Output is correct
2 Correct 437 ms 93940 KB Output is correct
3 Correct 415 ms 94096 KB Output is correct
4 Correct 431 ms 95016 KB Output is correct
5 Correct 459 ms 98096 KB Output is correct
6 Correct 207 ms 91508 KB Output is correct
7 Correct 208 ms 92540 KB Output is correct
8 Correct 224 ms 93232 KB Output is correct
9 Correct 234 ms 94872 KB Output is correct
10 Correct 227 ms 92520 KB Output is correct
11 Correct 358 ms 95980 KB Output is correct
12 Correct 319 ms 91756 KB Output is correct
13 Correct 329 ms 91588 KB Output is correct
14 Correct 347 ms 96092 KB Output is correct
15 Correct 340 ms 94192 KB Output is correct
16 Correct 10 ms 25284 KB Output is correct
17 Correct 225 ms 95956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27348 KB Output is correct
2 Correct 19 ms 27220 KB Output is correct
3 Correct 17 ms 27196 KB Output is correct
4 Correct 18 ms 27240 KB Output is correct
5 Correct 18 ms 27132 KB Output is correct
6 Correct 16 ms 27352 KB Output is correct
7 Correct 15 ms 27248 KB Output is correct
8 Correct 17 ms 27264 KB Output is correct
9 Correct 16 ms 27220 KB Output is correct
10 Correct 15 ms 27220 KB Output is correct
11 Correct 16 ms 27352 KB Output is correct
12 Correct 15 ms 27132 KB Output is correct
13 Correct 15 ms 27220 KB Output is correct
14 Correct 17 ms 27272 KB Output is correct
15 Correct 16 ms 27268 KB Output is correct
16 Correct 10 ms 25352 KB Output is correct
17 Correct 14 ms 27244 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27348 KB Output is correct
2 Correct 19 ms 27220 KB Output is correct
3 Correct 17 ms 27196 KB Output is correct
4 Correct 18 ms 27240 KB Output is correct
5 Correct 18 ms 27132 KB Output is correct
6 Correct 16 ms 27352 KB Output is correct
7 Correct 15 ms 27248 KB Output is correct
8 Correct 17 ms 27264 KB Output is correct
9 Correct 16 ms 27220 KB Output is correct
10 Correct 15 ms 27220 KB Output is correct
11 Correct 16 ms 27352 KB Output is correct
12 Correct 15 ms 27132 KB Output is correct
13 Correct 15 ms 27220 KB Output is correct
14 Correct 17 ms 27272 KB Output is correct
15 Correct 16 ms 27268 KB Output is correct
16 Correct 10 ms 25352 KB Output is correct
17 Correct 14 ms 27244 KB Output is correct
18 Correct 84 ms 29952 KB Output is correct
19 Correct 79 ms 29664 KB Output is correct
20 Correct 95 ms 30016 KB Output is correct
21 Correct 83 ms 29688 KB Output is correct
22 Correct 88 ms 29744 KB Output is correct
23 Correct 76 ms 29664 KB Output is correct
24 Correct 77 ms 29900 KB Output is correct
25 Correct 75 ms 29900 KB Output is correct
26 Correct 74 ms 29844 KB Output is correct
27 Correct 72 ms 29688 KB Output is correct
28 Correct 55 ms 29264 KB Output is correct
29 Correct 57 ms 29288 KB Output is correct
30 Correct 61 ms 29332 KB Output is correct
31 Correct 66 ms 29436 KB Output is correct
32 Correct 60 ms 29392 KB Output is correct
33 Correct 10 ms 25300 KB Output is correct
34 Correct 58 ms 29536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 98272 KB Output is correct
2 Correct 432 ms 96616 KB Output is correct
3 Correct 401 ms 91784 KB Output is correct
4 Correct 400 ms 91128 KB Output is correct
5 Correct 426 ms 93260 KB Output is correct
6 Correct 205 ms 91996 KB Output is correct
7 Correct 207 ms 91264 KB Output is correct
8 Correct 219 ms 91876 KB Output is correct
9 Correct 223 ms 91180 KB Output is correct
10 Correct 242 ms 96688 KB Output is correct
11 Correct 331 ms 91120 KB Output is correct
12 Correct 347 ms 97528 KB Output is correct
13 Correct 307 ms 91096 KB Output is correct
14 Correct 350 ms 93184 KB Output is correct
15 Correct 347 ms 97132 KB Output is correct
16 Correct 10 ms 25300 KB Output is correct
17 Correct 214 ms 92860 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 94996 KB Output is correct
2 Correct 437 ms 93940 KB Output is correct
3 Correct 415 ms 94096 KB Output is correct
4 Correct 431 ms 95016 KB Output is correct
5 Correct 459 ms 98096 KB Output is correct
6 Correct 207 ms 91508 KB Output is correct
7 Correct 208 ms 92540 KB Output is correct
8 Correct 224 ms 93232 KB Output is correct
9 Correct 234 ms 94872 KB Output is correct
10 Correct 227 ms 92520 KB Output is correct
11 Correct 358 ms 95980 KB Output is correct
12 Correct 319 ms 91756 KB Output is correct
13 Correct 329 ms 91588 KB Output is correct
14 Correct 347 ms 96092 KB Output is correct
15 Correct 340 ms 94192 KB Output is correct
16 Correct 10 ms 25284 KB Output is correct
17 Correct 225 ms 95956 KB Output is correct
18 Correct 18 ms 27348 KB Output is correct
19 Correct 19 ms 27220 KB Output is correct
20 Correct 17 ms 27196 KB Output is correct
21 Correct 18 ms 27240 KB Output is correct
22 Correct 18 ms 27132 KB Output is correct
23 Correct 16 ms 27352 KB Output is correct
24 Correct 15 ms 27248 KB Output is correct
25 Correct 17 ms 27264 KB Output is correct
26 Correct 16 ms 27220 KB Output is correct
27 Correct 15 ms 27220 KB Output is correct
28 Correct 16 ms 27352 KB Output is correct
29 Correct 15 ms 27132 KB Output is correct
30 Correct 15 ms 27220 KB Output is correct
31 Correct 17 ms 27272 KB Output is correct
32 Correct 16 ms 27268 KB Output is correct
33 Correct 10 ms 25352 KB Output is correct
34 Correct 14 ms 27244 KB Output is correct
35 Correct 84 ms 29952 KB Output is correct
36 Correct 79 ms 29664 KB Output is correct
37 Correct 95 ms 30016 KB Output is correct
38 Correct 83 ms 29688 KB Output is correct
39 Correct 88 ms 29744 KB Output is correct
40 Correct 76 ms 29664 KB Output is correct
41 Correct 77 ms 29900 KB Output is correct
42 Correct 75 ms 29900 KB Output is correct
43 Correct 74 ms 29844 KB Output is correct
44 Correct 72 ms 29688 KB Output is correct
45 Correct 55 ms 29264 KB Output is correct
46 Correct 57 ms 29288 KB Output is correct
47 Correct 61 ms 29332 KB Output is correct
48 Correct 66 ms 29436 KB Output is correct
49 Correct 60 ms 29392 KB Output is correct
50 Correct 10 ms 25300 KB Output is correct
51 Correct 58 ms 29536 KB Output is correct
52 Correct 455 ms 98272 KB Output is correct
53 Correct 432 ms 96616 KB Output is correct
54 Correct 401 ms 91784 KB Output is correct
55 Correct 400 ms 91128 KB Output is correct
56 Correct 426 ms 93260 KB Output is correct
57 Correct 205 ms 91996 KB Output is correct
58 Correct 207 ms 91264 KB Output is correct
59 Correct 219 ms 91876 KB Output is correct
60 Correct 223 ms 91180 KB Output is correct
61 Correct 242 ms 96688 KB Output is correct
62 Correct 331 ms 91120 KB Output is correct
63 Correct 347 ms 97528 KB Output is correct
64 Correct 307 ms 91096 KB Output is correct
65 Correct 350 ms 93184 KB Output is correct
66 Correct 347 ms 97132 KB Output is correct
67 Correct 10 ms 25300 KB Output is correct
68 Correct 214 ms 92860 KB Output is correct
69 Correct 682 ms 96720 KB Output is correct
70 Correct 641 ms 100468 KB Output is correct
71 Correct 592 ms 94772 KB Output is correct
72 Correct 617 ms 98520 KB Output is correct
73 Correct 729 ms 97232 KB Output is correct
74 Correct 454 ms 100924 KB Output is correct
75 Correct 396 ms 95676 KB Output is correct
76 Correct 410 ms 101548 KB Output is correct
77 Correct 419 ms 95380 KB Output is correct
78 Correct 411 ms 96460 KB Output is correct
79 Correct 429 ms 100056 KB Output is correct
80 Correct 377 ms 94484 KB Output is correct
81 Correct 387 ms 94096 KB Output is correct
82 Correct 433 ms 97972 KB Output is correct
83 Correct 409 ms 94584 KB Output is correct
84 Correct 10 ms 25300 KB Output is correct
85 Correct 273 ms 95424 KB Output is correct