제출 #1278659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278659		enxiayy	Examination (JOI19_examination)	C++20	0 / 100	3095 ms	11076 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

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

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }
template<class T> int lwb(const vector<T>& a, const T& b){ return int(lower_bound(all(a), b) - begin(a)); }


const int N = 2e5 + 5;

struct query {
    int t, a, b, c, id;

    bool operator < (const query& other) const {
        if (a == other.a) return t < other.t;
        else return a > other.a;
    }
} eq[N];

int n, q;

struct BIT {
    vector<ll> bit;

    BIT() {}
    BIT(int n) : bit(n + 5) {}

    void update(int pos, ll val) {
        for(; pos < sz(bit); pos += pos & (-pos))
            bit[pos] += val;
    } 

    ll get(int pos) {
        ll res = 0;
        for(; pos > 0; pos -= pos & (-pos)) 
            res += bit[pos];
        return res;
    }

    ll query(int l, int r) {
        return get(r) - get(l - 1);
    }
} bit;

int mx_a = 0, mx_b = 0, mx_c = 0;
ll ans[N];

void dnc(int l, int r) {
    if (l == r) 
        return;
    
    int mid = (l + r) >> 1;
    dnc(l, mid);
    dnc(mid + 1, r);

    vector<query> update, answers;
    vector<int> tmp;
    FOR(i, l, mid) if (eq[i].t == 1) update.eb(eq[i]);
    FOR(i, mid + 1, r) if (eq[i].t == 2) answers.eb(eq[i]);

    sort(all(update), [&](query u, query v) {
        return u.b >= v.b;
    });
    sort(all(answers), [&](query u, query v) {
        return u.b >= v.b;
    });

    int pos = 0;
    FOR(i, 0, sz(answers) - 1) {
        while(pos < sz(update) && update[pos].b >= answers[i].b) {
            bit.update(update[pos].c, 1);
            tmp.eb(update[pos].c);
            ++pos;
        }
        ans[answers[i].id] += bit.query(answers[i].c, mx_c);
    }

    for(auto v : tmp) bit.update(v, -1);

}

vector<int> compress_a, compress_b, compress_c;

void solve() {
    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> eq[i].a >> eq[i].b;
        eq[i].c = eq[i].a + eq[i].b;
        eq[i].t = 1;
        eq[i].id = i;

        compress_a.eb(eq[i].a);
        compress_b.eb(eq[i].b);
        compress_c.eb(eq[i].c);
    }

    FOR(i, n + 1, q + n) {
        cin >> eq[i].a >> eq[i].b >> eq[i].c;
        eq[i].t = 2;
        eq[i].id = i;

        compress_a.eb(eq[i].a);
        compress_b.eb(eq[i].b);
        compress_c.eb(eq[i].c);
    }

    sort(all(compress_a)); sort(all(compress_b)); sort(all(compress_c));
    compact(compress_a); compact(compress_b); compact(compress_c);
    mx_a = sz(compress_a); mx_b = sz(compress_b); mx_c = sz(compress_c);

    FOR(i, 1, n + q) {
        eq[i].a = lwb(compress_a, eq[i].a) + 1;
        eq[i].b = lwb(compress_b, eq[i].b) + 1;
        eq[i].c = lwb(compress_c, eq[i].c) + 1;
    }
    
    bit = BIT(mx_c);
    sort(eq + 1, eq + 1 + n + q);

    dnc(1, n + q);

    FOR(i, n + 1, q + n) {
        cout << ans[i] << el;
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

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

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

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