Submission #369656

#	Time	Username	Problem	Language	Result	Execution time	Memory
369656		CodePlatina	Examination (JOI19_examination)	C++14	100 / 100	393 ms	32992 KiB

examination

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define tlll tuple<long long, long long, long long>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

int ps[101010];
vector<int> prX;
vector<int> prY;
vector<int> prP;
vector<tiii> lsX[101010];
vector<int> pntX[101010];
vector<tiii> lsPX[101010];
vector<int> pntPX[101010];
vector<tiii> lsPY[101010];
vector<int> pntPY[101010];

int N;
int ind[202020];
void init(void)
{
    for(int i = 0; i < 202020; ++i)
        ind[i] = 0;
}
void upd(int pos)
{
    pos += N;
    ++ind[pos];
    while(pos >>= 1) ++ind[pos];
}
int qr(int l, int r)
{
    int ret = 0;
    for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1) ret += ind[x++];
        if(y & 1) ret += ind[--y];
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T; cin >> n >> T;
    pii A[n]; tiii B[T];
    for(auto &i : A) cin >> i.ff >> i.ss;
    for(auto &[a, b, c] : B) cin >> a >> b >> c;

    for(auto &i : A)
    {
        prX.push_back(i.ff);
        prY.push_back(i.ss);
        prP.push_back(i.ff + i.ss);
    }

    sort(prX.begin(), prX.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    sort(prY.begin(), prY.end());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());
    sort(prP.begin(), prP.end());
    prP.resize(unique(prP.begin(), prP.end()) - prP.begin());

    for(auto &i : A)
    {
        int x = lower_bound(prX.begin(), prX.end(), i.ff) - prX.begin();
        int y = lower_bound(prY.begin(), prY.end(), i.ss) - prY.begin();
        int p = lower_bound(prP.begin(), prP.end(), i.ff + i.ss) - prP.begin();
        ++ps[p];
        pntX[x].push_back(y);
        pntPX[x].push_back(p);
        pntPY[y].push_back(p);
    }
    for(int i = (int)prP.size() - 2; i >= 0; --i) ps[i] += ps[i + 1];

    int ans[T]{};
    for(int i = 0; i < T; ++i)
    {
        auto [a, b, c] = B[i];

        int x = lower_bound(prX.begin(), prX.end(), a) - prX.begin();
        int y = lower_bound(prY.begin(), prY.end(), b) - prY.begin();
        int p = lower_bound(prP.begin(), prP.end(), c) - prP.begin();

        if(c <= a + b)
        {
            lsX[x].push_back({i, y, (int)prY.size()});
        }
        else
        {
            lsPX[x].push_back({i, p, (int)prP.size()});
            lsPY[y].push_back({i, p, (int)prP.size()});
            ans[i] = ps[p];
        }
    }

    N = prY.size();
    for(int i = (int)prX.size(); i >= 0; --i)
    {
        for(auto j : pntX[i]) upd(j);
        for(auto [j, l, r] : lsX[i]) ans[j] += qr(l, r);
    }

    N = prP.size();
    init();
    for(int i = 0; i <= (int)prP.size(); ++i)
    {
        for(auto [j, l, r] : lsPX[i]) ans[j] -= qr(l, r);
        for(auto j : pntPX[i]) upd(j);
    }

    init();
    for(int i = 0; i <= (int)prP.size(); ++i)
    {
        for(auto [j, l, r] : lsPY[i]) ans[j] -= qr(l, r);
        for(auto j : pntPY[i]) upd(j);
    }

    for(int i = 0; i < T; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto &[a, b, c] : B) cin >> a >> b >> c;
      |               ^
examination.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |         auto [a, b, c] = B[i];
      |              ^
examination.cpp:118:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |         for(auto [j, l, r] : lsX[i]) ans[j] += qr(l, r);
      |                  ^
examination.cpp:125:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |         for(auto [j, l, r] : lsPX[i]) ans[j] -= qr(l, r);
      |                  ^
examination.cpp:132:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |         for(auto [j, l, r] : lsPY[i]) ans[j] -= qr(l, r);
      |                  ^

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