Submission #998515

#	Time	Username	Problem	Language	Result	Execution time	Memory
998515		kh0i	Examination (JOI19_examination)	C++17	100 / 100	231 ms	20220 KiB

examination

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

struct Fenwick{
    #define gb(x) (x) & -(x)
 
    int n;
    vector<ll> bit;
 
    void init(int _n){
        n = _n;
        bit.resize(n + 2, 0);
    }
 
    void upd(int x, ll val){
        if(x == 0)
            return;
        for(; x <= n; x += gb(x))
            bit[x] += val;
    }
 
    ll get(int l, int r){
        ll res = 0;
        --l;
        for(; r; r -= gb(r)) res += bit[r];
        for(; l; l -= gb(l)) res -= bit[l];
        return res;
    }
};

struct Point{
    int x, y, z, id;
    bool operator < (const Point &o){ return x == o.x ? (y == o.y ? (z == o.z ? id < o.id : z >= o.z) : y >= o.y) : x > o.x; }
};

const int N = 2e5 + 3;

int n, q, res[N];
vector<Point> p;
vector<int> xx;
Fenwick fen;

void cdq(int l, int r){
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    vector<Point> tmp;
    vector<int> ops;
    int a = l, b = mid + 1;
    while(a <= mid and b <= r){
        if(p[a].y >= p[b].y){
            if(p[a].id == -1){
                fen.upd(p[a].z, 1);
                ops.push_back(p[a].z);
            }
            tmp.push_back(p[a++]);
        }
        else{
            if(p[b].id >= 0){
                res[p[b].id] += fen.get(p[b].z, N);
            }
            tmp.push_back(p[b++]);
        }
    }
    while(a <= mid)
        tmp.push_back(p[a++]);
    while(b <= r){
        if(p[b].id >= 0)
            res[p[b].id] += fen.get(p[b].z, N);
        tmp.push_back(p[b++]);
    }

    for(int i = l; i <= r; ++i)
        p[i] = tmp[i - l];

    for(int x : ops)
        fen.upd(x, -1);

    vector<Point>().swap(tmp);
    vector<int>().swap(ops);
}

void solve(){
    cin >> n >> q;
    for(int i = 0; i < n; ++i){
        int s, t;
        cin >> s >> t;
        p.push_back({s, t, s + t, -1});
        xx.push_back(s + t);
    }
    for(int i = 0; i < q; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        p.push_back({a, b, c, i});
        xx.push_back(c);
    }
    sort(all(xx));
    xx.resize(unique(all(xx)) - xx.begin());
    for(int i = 0; i < sz(p); ++i){
        p[i].z = lower_bound(all(xx), p[i].z) - xx.begin() + 1;
        //debug(i, p[i].z);
    }
    sort(all(p));

    fen.init(N);
    cdq(0, sz(p) - 1);
    for(int i = 0; i < q; ++i)
        cout << res[i] << '\n';
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int32_t main()':
examination.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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