Submission #1272207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272207		icebear	Examination (JOI19_examination)	C++20	100 / 100	483 ms	43124 KiB

examination

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

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;
int n, q, res[N];
ii score[N];
array<int, 4> tests[N];

struct BIT2D {
    const static int MAX = 2e5 + 5;
    vector<int> nodes[MAX], ft[MAX];

    void fakeUpdate(int x, int y) {
        for(; x; x -= x & -x) nodes[x].push_back(y);
    }

    void fakeGet(int x, int y) {
        for(; x < MAX; x += x & -x) nodes[x].push_back(y);
    }

    void prepare(vector<ii> &updates, vector<ii> &queries) {
        for(auto &x : updates) fakeUpdate(x.first, x.second);
        for(auto &x : queries) fakeGet(x.first, x.second);
        FOR(i, 1, MAX - 5) {
            sort(nodes[i].begin(), nodes[i].end());
            ft[i].assign((int)nodes[i].size() + 5, 0);
        }
    }

    void update(int x, int y, int v) {
        for(; x; x -= x & -x)
            for(int t = upper_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin(); t; t -= t & -t)
                ft[x][t] += v;
    }

    int query(int x, int y) {
        int ans = 0;
        for(; x < MAX; x += x & -x)
            for(int t = upper_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin(); t <= (int)nodes[x].size(); t += t & -t)
                ans += ft[x][t];
        return ans;
    }
} bit2d;

vector<int> S, T;

void init(void) {
    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> score[i].fi >> score[i].se;
        S.pb(score[i].fi);
        T.pb(score[i].se);
    }
    FOR(i, 1, q) {
        cin >> tests[i][0] >> tests[i][1] >> tests[i][2], tests[i][3] = i;
        S.pb(tests[i][0]);
        T.pb(tests[i][1]);
    }
}

void process(void) {
    sort(score + 1, score + n + 1, [&](ii &x, ii &y){
        return x.fi + x.se > y.fi + y.se;
    });
    sort(tests + 1, tests + q + 1, [&](array<int, 4> &x, array<int, 4> &y){
        return x[2] > y[2];
    });

    sort(all(S)); sort(all(T));
    S.resize(unique(all(S)) - S.begin());
    T.resize(unique(all(T)) - T.begin());
    FOR(i, 1, n) {
        score[i].fi = upper_bound(all(S), score[i].fi) - S.begin();
        score[i].se = upper_bound(all(T), score[i].se) - T.begin();
    }
    FOR(i, 1, q) {
        tests[i][0] = upper_bound(all(S), tests[i][0]) - S.begin();
        tests[i][1] = upper_bound(all(T), tests[i][1]) - T.begin();
    }

    vector<ii> updates, queries;
    FOR(i, 1, n) updates.pb(score[i]);
    FOR(i, 1, q) queries.pb(mp(tests[i][0], tests[i][1]));

    bit2d.prepare(updates, queries);

    int j = 1;
    FOR(i, 1, q) {
        while(j <= n && S[score[j].fi - 1] + T[score[j].se - 1] >= tests[i][2]) {
            bit2d.update(score[j].fi, score[j].se, +1);
            j++;
        }
        res[tests[i][3]] = bit2d.query(tests[i][0], tests[i][1]);
    }

    FOR(i, 1, q) cout << res[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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