oj.uz

Submission #739726

# Submission time Handle Problem Language Result Execution time Memory
739726 2023-05-11T07:00:03 Z bgnbvnbv Examination (JOI19_examination) C++14
100 / 100
 140 ms 18520 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#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;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,q;
struct qq
{
    ll s,t;
    bool operator<(const qq&o)
    {
        return s>o.s;
    }
}x[maxN];
pli y[maxN],z[maxN];
ll bs(ll val)
{
    ll low=1,high=n;
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(x[mid].s<=val) high=mid-1;
        else low=mid+1;
    }
    return low;
}
struct qqq
{
    ll c,l,r,id;
    bool operator<(const qqq&o)
    {
        return c<o.c;
    }
};
vector<qqq>q1,q2;
ll bit[maxN];
void update(ll i,ll v)
{
    while(i<=n)
    {
        bit[i]+=v;
        i+=i&(-i);
    }
}
ll get(ll l,ll r)
{
    l--;
    ll ans=0;
    while(r>0)
    {
        ans+=bit[r];
        r-=r&(-r);
    }
    while(l>0)
    {
        ans-=bit[l];
        l-=(l&(-l));
    }
    return ans;
}
ll ans[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> x[i].s >> x[i].t;
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++)
    {
        y[i]={x[i].t,i};
        z[i]={x[i].t+x[i].s,i};
    }
    sort(y+1,y+n+1);
    sort(z+1,z+n+1);
    for(int i=1;i<=q;i++)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        ll r=bs(a-1);
        r--;
        ll l=bs(c-b);
        if(l<=r)
        {
            q1.pb({c,l,r,i});
        }
        l--;
        l=min(l,r);
        if(1<=l)
        {
            q2.pb({b,1,l,i});
        }
    }
    sort(q1.begin(),q1.end());
    sort(q2.begin(),q2.end());
    ll j=n;
    for(int i=(int)q1.size()-1;i>=0;i--)
    {
        while(j>0&&z[j].fi>=q1[i].c)
        {
            update(z[j].se,1);
            j--;
        }
        ans[q1[i].id]+=get(q1[i].l,q1[i].r);
    }
    for(int i=n;i>j;i--)
    {
        update(z[i].se,-1);
    }
    j=n;
    for(int i=(int)q2.size()-1;i>=0;i--)
    {
        while(j>0&&y[j].fi>=q2[i].c)
        {
            update(y[j].se,1);
            j--;
        }
        ans[q2[i].id]+=get(q2[i].l,q2[i].r);
    }
    for(int i=1;i<=q;i++) cout << ans[i] <<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

examination.cpp: In function 'll bs(ll)':
examination.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         ll mid=low+high>>1;
      |                ~~~^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 2 ms 732 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 10484 KB Output is correct
2 Correct 97 ms 12836 KB Output is correct
3 Correct 95 ms 12908 KB Output is correct
4 Correct 81 ms 12168 KB Output is correct
5 Correct 79 ms 12164 KB Output is correct
6 Correct 70 ms 11428 KB Output is correct
7 Correct 89 ms 12804 KB Output is correct
8 Correct 91 ms 12872 KB Output is correct
9 Correct 86 ms 12700 KB Output is correct
10 Correct 66 ms 10396 KB Output is correct
11 Correct 76 ms 12004 KB Output is correct
12 Correct 43 ms 8760 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 10484 KB Output is correct
2 Correct 97 ms 12836 KB Output is correct
3 Correct 95 ms 12908 KB Output is correct
4 Correct 81 ms 12168 KB Output is correct
5 Correct 79 ms 12164 KB Output is correct
6 Correct 70 ms 11428 KB Output is correct
7 Correct 89 ms 12804 KB Output is correct
8 Correct 91 ms 12872 KB Output is correct
9 Correct 86 ms 12700 KB Output is correct
10 Correct 66 ms 10396 KB Output is correct
11 Correct 76 ms 12004 KB Output is correct
12 Correct 43 ms 8760 KB Output is correct
13 Correct 123 ms 14108 KB Output is correct
14 Correct 120 ms 14748 KB Output is correct
15 Correct 98 ms 12856 KB Output is correct
16 Correct 106 ms 14132 KB Output is correct
17 Correct 95 ms 12612 KB Output is correct
18 Correct 73 ms 12984 KB Output is correct
19 Correct 112 ms 14208 KB Output is correct
20 Correct 120 ms 16000 KB Output is correct
21 Correct 121 ms 14716 KB Output is correct
22 Correct 65 ms 10436 KB Output is correct
23 Correct 72 ms 11940 KB Output is correct
24 Correct 42 ms 8764 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 2 ms 732 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 600 KB Output is correct
19 Correct 98 ms 10484 KB Output is correct
20 Correct 97 ms 12836 KB Output is correct
21 Correct 95 ms 12908 KB Output is correct
22 Correct 81 ms 12168 KB Output is correct
23 Correct 79 ms 12164 KB Output is correct
24 Correct 70 ms 11428 KB Output is correct
25 Correct 89 ms 12804 KB Output is correct
26 Correct 91 ms 12872 KB Output is correct
27 Correct 86 ms 12700 KB Output is correct
28 Correct 66 ms 10396 KB Output is correct
29 Correct 76 ms 12004 KB Output is correct
30 Correct 43 ms 8760 KB Output is correct
31 Correct 123 ms 14108 KB Output is correct
32 Correct 120 ms 14748 KB Output is correct
33 Correct 98 ms 12856 KB Output is correct
34 Correct 106 ms 14132 KB Output is correct
35 Correct 95 ms 12612 KB Output is correct
36 Correct 73 ms 12984 KB Output is correct
37 Correct 112 ms 14208 KB Output is correct
38 Correct 120 ms 16000 KB Output is correct
39 Correct 121 ms 14716 KB Output is correct
40 Correct 65 ms 10436 KB Output is correct
41 Correct 72 ms 11940 KB Output is correct
42 Correct 42 ms 8764 KB Output is correct
43 Correct 125 ms 16160 KB Output is correct
44 Correct 132 ms 16052 KB Output is correct
45 Correct 122 ms 16600 KB Output is correct
46 Correct 109 ms 15404 KB Output is correct
47 Correct 98 ms 13912 KB Output is correct
48 Correct 73 ms 12480 KB Output is correct
49 Correct 122 ms 18520 KB Output is correct
50 Correct 120 ms 16044 KB Output is correct
51 Correct 140 ms 18128 KB Output is correct
52 Correct 80 ms 11952 KB Output is correct
53 Correct 75 ms 12860 KB Output is correct