oj.uz

Submission #998490

# Submission time Handle Problem Language Result Execution time Memory
998490 2024-06-14T04:21:35 Z kh0i Examination (JOI19_examination) C++17
2 / 100
 3000 ms 2936 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){
            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 <= l)
        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;
        int res = 0;
        for(int i = 0; i < n; ++i)
            res += (p[i].x >= a and p[i].y >= b and p[i].z >= c);
        cout << res << '\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:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 31 ms 732 KB Output is correct
8 Correct 31 ms 720 KB Output is correct
9 Correct 32 ms 604 KB Output is correct
10 Correct 31 ms 600 KB Output is correct
11 Correct 31 ms 604 KB Output is correct
12 Correct 31 ms 600 KB Output is correct
13 Correct 31 ms 604 KB Output is correct
14 Correct 31 ms 712 KB Output is correct
15 Correct 32 ms 600 KB Output is correct
16 Correct 16 ms 656 KB Output is correct
17 Correct 22 ms 684 KB Output is correct
18 Correct 10 ms 860 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 31 ms 732 KB Output is correct
8 Correct 31 ms 720 KB Output is correct
9 Correct 32 ms 604 KB Output is correct
10 Correct 31 ms 600 KB Output is correct
11 Correct 31 ms 604 KB Output is correct
12 Correct 31 ms 600 KB Output is correct
13 Correct 31 ms 604 KB Output is correct
14 Correct 31 ms 712 KB Output is correct
15 Correct 32 ms 600 KB Output is correct
16 Correct 16 ms 656 KB Output is correct
17 Correct 22 ms 684 KB Output is correct
18 Correct 10 ms 860 KB Output is correct
19 Execution timed out 3073 ms 2936 KB Time limit exceeded
20 Halted 0 ms 0 KB -