oj.uz

답안 #779463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779463 2023-07-11T12:57:19 Z sofija6 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 22600 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;
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.insert(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.insert(z[i]);
    }
    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

# 결과 실행 시간 메모리 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 1884 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 27 ms 3028 KB Output is correct
8 Correct 27 ms 3044 KB Output is correct
9 Correct 27 ms 3028 KB Output is correct
10 Correct 27 ms 3004 KB Output is correct
11 Correct 9 ms 2900 KB Output is correct
12 Correct 5 ms 2260 KB Output is correct
13 Correct 24 ms 2692 KB Output is correct
14 Correct 24 ms 2712 KB Output is correct
15 Correct 28 ms 2700 KB Output is correct
16 Correct 5 ms 2644 KB Output is correct
17 Correct 27 ms 2996 KB Output is correct
18 Correct 3 ms 2260 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3054 ms 22600 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 1884 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 27 ms 3028 KB Output is correct
8 Correct 27 ms 3044 KB Output is correct
9 Correct 27 ms 3028 KB Output is correct
10 Correct 27 ms 3004 KB Output is correct
11 Correct 9 ms 2900 KB Output is correct
12 Correct 5 ms 2260 KB Output is correct
13 Correct 24 ms 2692 KB Output is correct
14 Correct 24 ms 2712 KB Output is correct
15 Correct 28 ms 2700 KB Output is correct
16 Correct 5 ms 2644 KB Output is correct
17 Correct 27 ms 2996 KB Output is correct
18 Correct 3 ms 2260 KB Output is correct
19 Execution timed out 3054 ms 22600 KB Time limit exceeded
20 Halted 0 ms 0 KB -