Submission #578354

#	Time	Username	Problem	Language	Result	Execution time	Memory
578354		OttoTheDino	Examination (JOI19_examination)	C++17	100 / 100	712 ms	48180 KiB

examination

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define aint(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<int> vint;

const int mx = 4e5;
int ftree[mx+1][2];

void upd (int tp, int val, int x) {
    while (x <= mx) {
        ftree[x][tp] += val;
        x += x&(-x);
    }
}

int pref (int tp, int x) {
    int sum = 0;
    while (x>0) {
        sum += ftree[x][tp];
        x -= x&(-x);
    }
    return sum;
}

int query (int tp, int l, int r) {
    return pref(tp, r)-pref(tp, l-1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q, x = 1; cin >> n >> q;

    vector<pair<int,ii>> peep;
    vector<pair<ii,ii>> ques;

    set<int> sta, stb;

    int ans[q+1];

    rep (i,1,n) {
        int a, b; cin >> a >> b;
        peep.pb({a+b,{a,b}});
        sta.insert(a);
        stb.insert(b);
    }

    rep (i,1,q) {
        int a, b, c; cin >> a >> b >> c;
        ques.pb({{max(a+b,c),i},{a,b}});
        sta.insert(a);
        stb.insert(b);
    }

    map<int,int> mpa, mpb;
    for (int a : sta) mpa[a] = x++;
    x = 1;
    for (int b : stb) mpb[b] = x++;
    x = 0;

    sort(aint(ques));
    reverse(aint(ques));
    sort(aint(peep));
    reverse(aint(peep));

    rep (i,0,q-1) {
        int c = ques[i].fi.fi, a = mpa[ques[i].se.fi], b = mpb[ques[i].se.se], u = ques[i].fi.se;
        while (x < n && peep[x].fi>=c) {
            upd (0, 1, mpa[peep[x].se.fi]);
            upd (1, 1, mpb[peep[x].se.se]);
            x++;
        }
        ans[u] = query(0,a,mx) + query(1,b,mx) - x;
    }

    rep (i,1,q) cout << ans[i] << "\n";

    return 0;
}

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