Submission #471590

#	Time	Username	Problem	Language	Result	Execution time	Memory
471590		Rainbowbunny	Examination (JOI19_examination)	C++17	100 / 100	766 ms	48820 KiB

examination

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, q;
int ans[MAXN];
vector <int> VX, VY;
vector <int> BIT2D[MAXN], V2D[MAXN];
vector <pair <int, pair <int, int> > > Student;
vector <pair <pair <int, int>, pair <int, int> > > Queries;
vector <pair <pair <int, int>, pair <int, int> > > QBIT;

void FakeAdd(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        V2D[x].push_back(y);
    }
}

void FakeGet(int x, int y)
{
    for(x; x > 0; x -= x & -x)
    {
        V2D[x].push_back(y);
    }
}

void Add(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        int tmp = lower_bound(V2D[x].begin(), V2D[x].end(), y) - V2D[x].begin() + 1;
        for(tmp; tmp < (int)BIT2D[x].size(); tmp += tmp & -tmp)
        {
            BIT2D[x][tmp]++;
        }
    }
}

int Get(int x, int y)
{
    int ans = 0;
    for(x; x > 0; x -= x & -x)
    {
        int tmp = lower_bound(V2D[x].begin(), V2D[x].end(), y) - V2D[x].begin() + 1;
        for(tmp; tmp > 0; tmp -= tmp & -tmp)
        {
            ans += BIT2D[x][tmp];
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        Student.emplace_back(x + y, make_pair(x, y));
        VX.push_back(x);
        VY.push_back(y);
    }
    for(int i = 1; i <= q; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        VX.push_back(x);
        VY.push_back(y);
        Queries.emplace_back(make_pair(z, i), make_pair(x, y));
    }
    sort(Student.begin(), Student.end());
    sort(Queries.begin(), Queries.end());
    sort(VX.begin(), VX.end());
    sort(VY.begin(), VY.end());
    VX.erase(unique(VX.begin(), VX.end()), VX.end());
    VY.erase(unique(VY.begin(), VY.end()), VY.end());
    while(Student.empty() == false and Queries.empty() == false)
    {
        if(Student.back().first >= Queries.back().first.first)
        {
            QBIT.emplace_back(make_pair(1, 0), Student.back().second);
            Student.pop_back();
        }
        else
        {
            QBIT.emplace_back(make_pair(2, Queries.back().first.second), Queries.back().second);
            Queries.pop_back();
        }
    }
    while(Queries.empty() == false)
    {
        QBIT.emplace_back(make_pair(2, Queries.back().first.second), Queries.back().second);
        Queries.pop_back();
    }
    for(auto &e : QBIT)
    {
        e.second.first = VX.end() - lower_bound(VX.begin(), VX.end(), e.second.first);
        e.second.second = VY.end() - lower_bound(VY.begin(), VY.end(), e.second.second);
        if(e.first.first == 1)
        {
            FakeAdd(e.second.first, e.second.second);
        }
        else
        {
            FakeGet(e.second.first, e.second.second);
        }
    }
    for(int i = 1; i < MAXN; i++)
    {
        sort(V2D[i].begin(), V2D[i].end());
        V2D[i].erase(unique(V2D[i].begin(), V2D[i].end()), V2D[i].end());
        BIT2D[i].resize((int)V2D[i].size() + 1);
    }
    for(auto e : QBIT)
    {
        if(e.first.first == 1)
        {
            Add(e.second.first, e.second.second);
        }
        else
        {
            ans[e.first.second] = Get(e.second.first, e.second.second);
        }
    }
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

examination.cpp: In function 'void FakeAdd(int, int)':
examination.cpp:16:9: warning: statement has no effect [-Wunused-value]
   16 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp: In function 'void FakeGet(int, int)':
examination.cpp:24:9: warning: statement has no effect [-Wunused-value]
   24 |     for(x; x > 0; x -= x & -x)
      |         ^
examination.cpp: In function 'void Add(int, int)':
examination.cpp:32:9: warning: statement has no effect [-Wunused-value]
   32 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp:35:13: warning: statement has no effect [-Wunused-value]
   35 |         for(tmp; tmp < (int)BIT2D[x].size(); tmp += tmp & -tmp)
      |             ^~~
examination.cpp: In function 'int Get(int, int)':
examination.cpp:45:9: warning: statement has no effect [-Wunused-value]
   45 |     for(x; x > 0; x -= x & -x)
      |         ^
examination.cpp:48:13: warning: statement has no effect [-Wunused-value]
   48 |         for(tmp; tmp > 0; tmp -= tmp & -tmp)
      |             ^~~

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