Submission #1094565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094565		BLOBVISGOD	Examination (JOI19_examination)	C++17	100 / 100	1286 ms	12512 KiB

examination

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 100000;
const int B = pow(N,.666);

int cnt[N];
int active = 0;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,q; cin >> n >> q;
    vector<array<int,2>> a(n);
    rep(i,0,n) rep(j,0,2) cin >> a[i][j];

    vvi ord(3,vi(n));
    rep(i,0,3) iota(all(ord[i]),0);
    rep(i,0,2) sort(all(ord[i]), [&](int l, int r){
        return a[l][i] < a[r][i];
    });
    sort(all(ord[2]),[&](int l, int r){
        return a[l][0] + a[l][1] < a[r][0] + a[r][1];
    });
    vvi vals(3,vi(n));
    rep(i,0,2) rep(j,0,n) vals[i][j] = a[ord[i][j]][i];
    rep(j,0,n) vals[2][j] =  a[ord[2][j]][0] + a[ord[2][j]][1];

    vector<array<int,3>> qs(q), s(q);
    vi qi(q);
    iota(all(qi),0);

    rep(i,0,q){ 
        rep(j,0,3) cin >> qs[i][j],
            qs[i][j] = lower_bound(all(vals[j]),qs[i][j]) - begin(vals[j]);

        int x = 0;
        rep(j,0,3){
            s[i][j] = qs[i][j]/B;
            if (x) s[i][j] = n - s[i][j];
            x ^= s[i][j]&1;
        }
    }

    sort(all(qi),[&](int l, int r){
        return s[l] < s[r];
    });

    array<int,3> cur = {n,n,n}; // none are active yet
    vi sol(q);

    for(auto id : qi){
        rep(j,0,3){
            while (cur[j] > qs[id][j]) {
                cur[j]--;
                cnt[ord[j][cur[j]]]++;
                if (cnt[ord[j][cur[j]]] == 3) active++;
            }while (cur[j] < qs[id][j]){
                cnt[ord[j][cur[j]]]--;            
                if (cnt[ord[j][cur[j]]] == 2) active--;
                cur[j]++;
            }
        }
        sol[id] = active;
    }
    
    for(auto c : sol) cout << c << '\n';
}

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