oj.uz

Submission #736139

# Submission time Handle Problem Language Result Execution time Memory
736139 2023-05-05T09:02:13 Z Vanilla Examination (JOI19_examination) C++17
20 / 100
 298 ms 20044 KB 
#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
// string __fname = ""; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out
#define int64 long long
#define uint64 unsigned long long
#define x first
#define y second
#define pb push_back
#define pii pair <int, int> 
#define pii64 pair <int64, int64>
#define db(x) cout << "> " << #x << ": " << (x) << "\n"
#define qr queries()
#define yn(x) if (x) {ctn("Yes");}else {ctn("No");}
void solve(int);
void queries(){int n;cin >> n;for (int i = 1; i <= n; i++) solve(i);}
template<class T>T ceildiv(T a, T b) {return a / b + !!(a % b);}
template<class T>T gcd (T a, T b){return (b ? gcd(b, a % b): a);}
template<class T>T lcm (T a, T b){return a * b / gcd(a, b);}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
const int ddx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double pi = 3.14159265359;
const double eps = 1e-6;
const int64 hash_inv = 940594066;
const int64 hash_p = 101;
const int64 mod = 1e9 + 7;
const int maxn = 2e5 + 2;
pii a [maxn];
int rs [maxn];

void solve(int id){
    
    return;
}

struct node {
    int l,r;
    int64 v;

    node* left = NULL;
    node* right = NULL;

    node(int _l, int _r, int64 _v): l(_l), r(_r), v(_v) {};
    
    inline void extend() {
        if (left != NULL) return;
        int mid = (l + r) / 2;
        left = new node(l, mid, 0);
        right = new node(mid + 1, r, 0);
    }

    inline int64 query (int il, int ir) {
        if (il <= l && r <= ir) return v;
        if (l > ir || r < il) return 0;
        extend();
        return left->query(il, ir) + right->query(il, ir);
    }

    inline void update (int x, int64 nval) {
        if (l == r && l == x) return void(v+=nval);
        if (l > x || r < x) return;
        extend();
        left->update(x, nval);
        right->update(x, nval);
        v = left->v + right->v;
    }
};

struct event {
    int type;
    int x;
    int l;
    int r;
    int idx;

    bool operator < (const event& oth) const {
        if (x != oth.x) return x < oth.x;
        return type < oth.type;
    }
};


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed; cout << setprecision(10); 
    node* sg = new node (0, maxn, 0);
    vector <event> sl;
    int n,q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].y;
        sl.push_back({2, a[i].x, a[i].y, a[i].y, -1});
    }
    for (int i = 0; i < q; i++){
        int x,y,z;
        cin >> x >> y >> z;
        sl.push_back({1, x, y, maxn - 1, i});
        sl.push_back({3, maxn - 1, y, maxn - 1, i});
    }
    sort(sl.begin(), sl.end());
    for (auto& [t, x, l, r, idx]: sl) {
        // cout << t << " " << x << " " << l << " " << r << " " << idx << "\n";
        if (t == 1) {
            rs[idx]-=sg->query(l, r);
        }
        else if (t == 2) {
            sg->update(l, 1);
        }
        else {
            rs[idx]+=sg->query(l, r);
        }
    }
    for (int i = 0; i < q; i++){
        cout << rs[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 19524 KB Output is correct
2 Correct 232 ms 19596 KB Output is correct
3 Correct 298 ms 19600 KB Output is correct
4 Correct 143 ms 13232 KB Output is correct
5 Correct 230 ms 18812 KB Output is correct
6 Correct 118 ms 12464 KB Output is correct
7 Correct 236 ms 19552 KB Output is correct
8 Correct 198 ms 19160 KB Output is correct
9 Correct 211 ms 19064 KB Output is correct
10 Correct 226 ms 18780 KB Output is correct
11 Correct 106 ms 13164 KB Output is correct
12 Correct 101 ms 12364 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 19524 KB Output is correct
2 Correct 232 ms 19596 KB Output is correct
3 Correct 298 ms 19600 KB Output is correct
4 Correct 143 ms 13232 KB Output is correct
5 Correct 230 ms 18812 KB Output is correct
6 Correct 118 ms 12464 KB Output is correct
7 Correct 236 ms 19552 KB Output is correct
8 Correct 198 ms 19160 KB Output is correct
9 Correct 211 ms 19064 KB Output is correct
10 Correct 226 ms 18780 KB Output is correct
11 Correct 106 ms 13164 KB Output is correct
12 Correct 101 ms 12364 KB Output is correct
13 Incorrect 248 ms 20044 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -