oj.uz

답안 #779484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779484 2023-07-11T13:20:35 Z sofija6 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 13956 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
using namespace std;
pair<ll,ll> a[MAXN],b[MAXN];
set<ll> sums;
vector<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 Compressed(ll x)
{
    auto it=lower_bound(comp.begin(),comp.end(),x);
    return it-comp.begin()+1;
}
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(Compressed(sumab[i]),1);
}
void Remove(ll pos,pair<ll,ll> *p)
{
    ll i=p[pos].second;
    cntind[i]--;
    if (cntind[i]==1)
        B.Add(Compressed(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;
        comp.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];
        comp.push_back(z[i]);
    }
    sort(comp.begin(),comp.end());
    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(Compressed(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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 21 ms 2420 KB Output is correct
8 Correct 21 ms 2388 KB Output is correct
9 Correct 21 ms 2388 KB Output is correct
10 Correct 20 ms 2444 KB Output is correct
11 Correct 7 ms 2388 KB Output is correct
12 Correct 5 ms 2408 KB Output is correct
13 Correct 20 ms 2452 KB Output is correct
14 Correct 23 ms 2504 KB Output is correct
15 Correct 20 ms 2420 KB Output is correct
16 Correct 5 ms 2388 KB Output is correct
17 Correct 23 ms 2388 KB Output is correct
18 Correct 3 ms 2388 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3049 ms 13956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3049 ms 13956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 21 ms 2420 KB Output is correct
8 Correct 21 ms 2388 KB Output is correct
9 Correct 21 ms 2388 KB Output is correct
10 Correct 20 ms 2444 KB Output is correct
11 Correct 7 ms 2388 KB Output is correct
12 Correct 5 ms 2408 KB Output is correct
13 Correct 20 ms 2452 KB Output is correct
14 Correct 23 ms 2504 KB Output is correct
15 Correct 20 ms 2420 KB Output is correct
16 Correct 5 ms 2388 KB Output is correct
17 Correct 23 ms 2388 KB Output is correct
18 Correct 3 ms 2388 KB Output is correct
19 Execution timed out 3049 ms 13956 KB Time limit exceeded
20 Halted 0 ms 0 KB -