oj.uz

답안 #779487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779487 2023-07-11T13:21:10 Z sofija6 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 13748 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
using namespace std;
pair<ll,ll> a[MAXN],b[MAXN];
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 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 20 ms 2364 KB Output is correct
8 Correct 22 ms 2388 KB Output is correct
9 Correct 20 ms 2260 KB Output is correct
10 Correct 20 ms 2260 KB Output is correct
11 Correct 7 ms 2260 KB Output is correct
12 Correct 5 ms 2368 KB Output is correct
13 Correct 19 ms 2368 KB Output is correct
14 Correct 19 ms 2368 KB Output is correct
15 Correct 19 ms 2368 KB Output is correct
16 Correct 4 ms 2340 KB Output is correct
17 Correct 20 ms 2360 KB Output is correct
18 Correct 3 ms 2260 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3070 ms 13748 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 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 20 ms 2364 KB Output is correct
8 Correct 22 ms 2388 KB Output is correct
9 Correct 20 ms 2260 KB Output is correct
10 Correct 20 ms 2260 KB Output is correct
11 Correct 7 ms 2260 KB Output is correct
12 Correct 5 ms 2368 KB Output is correct
13 Correct 19 ms 2368 KB Output is correct
14 Correct 19 ms 2368 KB Output is correct
15 Correct 19 ms 2368 KB Output is correct
16 Correct 4 ms 2340 KB Output is correct
17 Correct 20 ms 2360 KB Output is correct
18 Correct 3 ms 2260 KB Output is correct
19 Execution timed out 3070 ms 13748 KB Time limit exceeded
20 Halted 0 ms 0 KB -