oj.uz

Submission #998493

# Submission time Handle Problem Language Result Execution time Memory
998493 2024-06-14T04:29:25 Z kh0i Examination (JOI19_examination) C++17
0 / 100
 170 ms 16428 KB 
#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 : 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

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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 6 ms 2396 KB Output is correct
8 Correct 6 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Incorrect 4 ms 2396 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 14252 KB Output is correct
2 Correct 170 ms 16428 KB Output is correct
3 Correct 165 ms 16376 KB Output is correct
4 Correct 149 ms 15612 KB Output is correct
5 Correct 149 ms 15612 KB Output is correct
6 Runtime error 65 ms 13568 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 14252 KB Output is correct
2 Correct 170 ms 16428 KB Output is correct
3 Correct 165 ms 16376 KB Output is correct
4 Correct 149 ms 15612 KB Output is correct
5 Correct 149 ms 15612 KB Output is correct
6 Runtime error 65 ms 13568 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 6 ms 2396 KB Output is correct
8 Correct 6 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Incorrect 4 ms 2396 KB Output isn't correct
13 Halted 0 ms 0 KB -