Submission #933531

#	Time	Username	Problem	Language	Result	Execution time	Memory
933531		Hanksburger	Examination (JOI19_examination)	C++17	0 / 100	438 ms	28072 KiB

examination

#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<long long, long long>, pair<long long, long long> > > vec;
long long bit[600005], ans[100005];
map<long long, long long> mp;
void upd(long long x, long long y)
{
    for (long long i=x; i<=6e5; i+=i&(-i))
        bit[i]+=y;
}
long long qry(long long x)
{
    long long res=0;
    for (long long i=x; i; i-=i&(-i))
        res+=bit[i];
    return res;
}
void recur(long long l, long long r)
{
    if (l==r)
        return;
    long long mid=(l+r)/2;
    vector<pair<pair<long long, long long>, long long> > a;
    vector<pair<long long, long long> > b;
    for (long long i=l; i<=mid; i++)
        if (vec[i].first.second)
            a.push_back({vec[i].second, vec[i].first.second});
    for (long long i=mid+1; i<=r; i++)
        if (!vec[i].first.second)
            b.push_back(vec[i].second);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long ind=b.size();
    for (long long i=a.size()-1; i>=0; i--)
    {
        while (ind && b[ind-1].first>=a[i].first.first)
        {
            upd(6e5+1-b[ind-1].second, 1);
            ind--;
        }
        ans[a[i].second]+=qry(6e5+1-a[i].first.second);
    }
    for (long long i=ind; i<b.size(); i++)
        upd(6e5+1-b[i].second, -1);
    recur(l, mid);
    recur(mid+1, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, cnt=0;
    cin >> n >> m;
    for (long long i=1; i<=n; i++)
    {
        long long x, y;
        cin >> x >> y;
        vec.push_back({{x+y, 0}, {x, y}});
        mp[x]=mp[y]=mp[x+y]=0;
    }
    for (long long i=1; i<=m; i++)
    {
        long long x, y, z;
        cin >> x >> y >> z;
        vec.push_back({{z, i}, {x, y}});
        mp[x]=mp[y]=mp[z]=0;
    }
    for (auto it=mp.begin(); it!=mp.end(); it++)
        (*it).second=(++cnt);
    for (long long i=0; i<vec.size(); i++)
    {
        vec[i].first.first=mp[vec[i].first.first];
        vec[i].second.first=mp[vec[i].second.first];
        vec[i].second.second=mp[vec[i].second.second];
    }
    sort(vec.begin(), vec.end());
    recur(0, vec.size()-1);
    for (long long i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In function 'void recur(long long int, long long int)':
examination.cpp:43:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (long long i=ind; i<b.size(); i++)
      |                           ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:71:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (long long i=0; i<vec.size(); i++)
      |                         ~^~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57