Submission #933533

#	Time	Username	Problem	Language	Result	Execution time	Memory
933533		Hanksburger	Examination (JOI19_examination)	C++17	100 / 100	1042 ms	43388 KiB

examination

#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>, pair<int, int> > > vec;
int bit[600005], ans[100005];
map<int, int> mp;
void upd(int x, int y)
{
    for (int i=x; i<=6e5; i+=i&(-i))
        bit[i]+=y;
}
int qry(int x)
{
    int res=0;
    for (int i=x; i; i-=i&(-i))
        res+=bit[i];
    return res;
}
void recur(int l, int r)
{
    if (l==r)
        return;
    int mid=(l+r)/2;
    vector<pair<pair<int, int>, int> > a;
    vector<pair<int, int> > b;
    for (int i=l; i<=mid; i++)
        if (vec[i].first.second<1e9)
            a.push_back({vec[i].second, vec[i].first.second});
    for (int i=mid+1; i<=r; i++)
        if (vec[i].first.second==1e9)
            b.push_back(vec[i].second);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int ind=b.size();
    for (int 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 (int 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);
    int n, m, cnt=0;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        int x, y;
        cin >> x >> y;
        vec.push_back({{x+y, 1e9}, {x, y}});
        mp[x]=mp[y]=mp[x+y]=0;
    }
    for (int i=1; i<=m; i++)
    {
        int 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 (int 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 (int i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

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

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