제출 #1272188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272188		icebear	Examination (JOI19_examination)	C++20	0 / 100	121 ms	29380 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 = 1e5 + 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;

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

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];
    });

    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 && score[j].fi + score[j].se >= 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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