oj.uz

Submission #779535

# Submission time Handle Problem Language Result Execution time Memory
779535 2023-07-11T13:55:57 Z sofija6 Examination (JOI19_examination) C++14
43 / 100
 3000 ms 15884 KB 
#include <bits/stdc++.h>
#define ll int
#define MAXN 100010
using namespace std;
pair<ll,ll> a[MAXN],b[MAXN];
vector<ll> sums;
unordered_map<ll,ll> comp;
ll n,q,x[MAXN],y[MAXN],z[MAXN],len,cntind[MAXN],ans[MAXN],sumab[MAXN];
bool Cmp(pair<ll,ll> p1,pair<ll,ll> p2)
{
    return p1.first>p2.first;
}
ll Find_Pos(ll x,pair<ll,ll> *p)
{
    ll l=1,r=n,mid,ans=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (p[mid].first>=x)
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ans;
}
struct bit
{
    vector<ll> sum;
    void Init()
    {
        sum.resize(2*MAXN);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<2*MAXN;i+=i&(-i))
            sum[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=sum[i];
        return ans;
    }
    ll Query(ll l,ll r)
    {
        return Calc(r)-Calc(l-1);
    }
};
bit B;
struct query
{
    ll l,r,ind;
};
query qq[MAXN];
bool Cmp_Query(query q1,query q2)
{
    if (q1.l/len!=q2.l/len)
        return q1.l/len<q2.l/len;
    return q1.r<q2.r;
}
void Add(ll pos,pair<ll,ll> *p)
{
    ll i=p[pos].second;
    cntind[i]++;
    if (cntind[i]==2)
        B.Add(comp[sumab[i]],1);
}
void Remove(ll pos,pair<ll,ll> *p)
{
    ll i=p[pos].second;
    cntind[i]--;
    if (cntind[i]==1)
        B.Add(comp[sumab[i]],-1);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    len=sqrt(n);
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i].first >> b[i].first;
        a[i].second=b[i].second=i;
        sumab[i]=a[i].first+b[i].first;
        sums.push_back(sumab[i]);
    }
    sort(a+1,a+1+n,Cmp);
    sort(b+1,b+1+n,Cmp);
    for (ll i=1;i<=q;i++)
    {
        cin >> x[i] >> y[i] >> z[i];
        sums.push_back(z[i]);
    }
    sort(sums.begin(),sums.end());
    ll cnt=1;
    for (auto i : sums)
        comp[i]=cnt++;
    for (ll i=1;i<=q;i++)
    {
        qq[i].l=Find_Pos(x[i],a);
        qq[i].r=Find_Pos(y[i],b);
        qq[i].ind=i;
    }
    sort(qq+1,qq+1+q,Cmp_Query);
    ll curl=0,curr=0;
    B.Init();
    for (ll i=1;i<=q;i++)
    {
        while (curl<qq[i].l)
        {
            curl++;
            Add(curl,a);
        }
        while (curr<qq[i].r)
        {
            curr++;
            Add(curr,b);
        }
        while (curl>qq[i].l)
        {
            Remove(curl,a);
            curl--;
        }
        while (curr>qq[i].r)
        {
            Remove(curr,b);
            curr--;
        }
        ans[qq[i].ind]=B.Query(comp[z[qq[i].ind]],2*MAXN-1);
    }
    for (ll i=1;i<=q;i++)
        cout << ans[i] << "\n";
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 14 ms 1628 KB Output is correct
8 Correct 15 ms 1620 KB Output is correct
9 Correct 14 ms 1620 KB Output is correct
10 Correct 14 ms 1624 KB Output is correct
11 Correct 6 ms 1620 KB Output is correct
12 Correct 4 ms 1368 KB Output is correct
13 Correct 13 ms 1492 KB Output is correct
14 Correct 13 ms 1472 KB Output is correct
15 Correct 15 ms 1364 KB Output is correct
16 Correct 3 ms 1492 KB Output is correct
17 Correct 13 ms 1620 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2849 ms 10460 KB Output is correct
2 Correct 2814 ms 10456 KB Output is correct
3 Correct 2800 ms 10560 KB Output is correct
4 Correct 2326 ms 10132 KB Output is correct
5 Correct 170 ms 10116 KB Output is correct
6 Correct 109 ms 7588 KB Output is correct
7 Correct 745 ms 10460 KB Output is correct
8 Correct 694 ms 10504 KB Output is correct
9 Correct 460 ms 10468 KB Output is correct
10 Correct 104 ms 9928 KB Output is correct
11 Correct 2283 ms 10024 KB Output is correct
12 Correct 56 ms 7240 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2849 ms 10460 KB Output is correct
2 Correct 2814 ms 10456 KB Output is correct
3 Correct 2800 ms 10560 KB Output is correct
4 Correct 2326 ms 10132 KB Output is correct
5 Correct 170 ms 10116 KB Output is correct
6 Correct 109 ms 7588 KB Output is correct
7 Correct 745 ms 10460 KB Output is correct
8 Correct 694 ms 10504 KB Output is correct
9 Correct 460 ms 10468 KB Output is correct
10 Correct 104 ms 9928 KB Output is correct
11 Correct 2283 ms 10024 KB Output is correct
12 Correct 56 ms 7240 KB Output is correct
13 Correct 2876 ms 12708 KB Output is correct
14 Correct 2688 ms 12336 KB Output is correct
15 Correct 2813 ms 10460 KB Output is correct
16 Correct 2387 ms 11556 KB Output is correct
17 Correct 168 ms 11564 KB Output is correct
18 Correct 112 ms 7676 KB Output is correct
19 Correct 2936 ms 12704 KB Output is correct
20 Correct 2856 ms 12500 KB Output is correct
21 Correct 1317 ms 12708 KB Output is correct
22 Correct 106 ms 10016 KB Output is correct
23 Correct 2233 ms 10008 KB Output is correct
24 Correct 57 ms 7284 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 14 ms 1628 KB Output is correct
8 Correct 15 ms 1620 KB Output is correct
9 Correct 14 ms 1620 KB Output is correct
10 Correct 14 ms 1624 KB Output is correct
11 Correct 6 ms 1620 KB Output is correct
12 Correct 4 ms 1368 KB Output is correct
13 Correct 13 ms 1492 KB Output is correct
14 Correct 13 ms 1472 KB Output is correct
15 Correct 15 ms 1364 KB Output is correct
16 Correct 3 ms 1492 KB Output is correct
17 Correct 13 ms 1620 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct
19 Correct 2849 ms 10460 KB Output is correct
20 Correct 2814 ms 10456 KB Output is correct
21 Correct 2800 ms 10560 KB Output is correct
22 Correct 2326 ms 10132 KB Output is correct
23 Correct 170 ms 10116 KB Output is correct
24 Correct 109 ms 7588 KB Output is correct
25 Correct 745 ms 10460 KB Output is correct
26 Correct 694 ms 10504 KB Output is correct
27 Correct 460 ms 10468 KB Output is correct
28 Correct 104 ms 9928 KB Output is correct
29 Correct 2283 ms 10024 KB Output is correct
30 Correct 56 ms 7240 KB Output is correct
31 Correct 2876 ms 12708 KB Output is correct
32 Correct 2688 ms 12336 KB Output is correct
33 Correct 2813 ms 10460 KB Output is correct
34 Correct 2387 ms 11556 KB Output is correct
35 Correct 168 ms 11564 KB Output is correct
36 Correct 112 ms 7676 KB Output is correct
37 Correct 2936 ms 12704 KB Output is correct
38 Correct 2856 ms 12500 KB Output is correct
39 Correct 1317 ms 12708 KB Output is correct
40 Correct 106 ms 10016 KB Output is correct
41 Correct 2233 ms 10008 KB Output is correct
42 Correct 57 ms 7284 KB Output is correct
43 Execution timed out 3042 ms 15884 KB Time limit exceeded
44 Halted 0 ms 0 KB -