oj.uz

Submission #736290

# Submission time Handle Problem Language Result Execution time Memory
736290 2023-05-05T12:02:53 Z Vanilla Examination (JOI19_examination) C++17
41 / 100
 335 ms 27272 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* xsg = new node (0, maxn, 0), *ysg = 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({0, a[i].x + a[i].y, a[i].x, a[i].y, -1});
    }
    for (int i = 0; i < q; i++){
        int x,y,z;
        cin >> x >> y >> z;
        sl.push_back({1, max(x + y, z), x, y, i});
    }
    sort(sl.begin(), sl.end());
    int sf = 0;
    for (auto& [t, x, l, r, idx]: sl) {
        // cout << t << " " << x << " " << l << " " << r << " " << idx << "\n";
        if (t == 0) {
            xsg->update(l, 1);
            ysg->update(r, 1);
            sf++;
        }
        else  {
            rs[idx] = xsg->query(l, maxn - 1) + ysg->query(r, maxn - 1) - sf;
        }
    }
    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 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 26844 KB Output is correct
2 Correct 254 ms 26904 KB Output is correct
3 Correct 280 ms 26988 KB Output is correct
4 Correct 152 ms 16952 KB Output is correct
5 Correct 169 ms 16932 KB Output is correct
6 Correct 120 ms 7076 KB Output is correct
7 Correct 292 ms 26476 KB Output is correct
8 Correct 268 ms 26412 KB Output is correct
9 Correct 213 ms 25960 KB Output is correct
10 Correct 144 ms 16740 KB Output is correct
11 Correct 147 ms 16752 KB Output is correct
12 Correct 100 ms 7032 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 26844 KB Output is correct
2 Correct 254 ms 26904 KB Output is correct
3 Correct 280 ms 26988 KB Output is correct
4 Correct 152 ms 16952 KB Output is correct
5 Correct 169 ms 16932 KB Output is correct
6 Correct 120 ms 7076 KB Output is correct
7 Correct 292 ms 26476 KB Output is correct
8 Correct 268 ms 26412 KB Output is correct
9 Correct 213 ms 25960 KB Output is correct
10 Correct 144 ms 16740 KB Output is correct
11 Correct 147 ms 16752 KB Output is correct
12 Correct 100 ms 7032 KB Output is correct
13 Correct 286 ms 27272 KB Output is correct
14 Correct 297 ms 27220 KB Output is correct
15 Correct 295 ms 26824 KB Output is correct
16 Correct 164 ms 17284 KB Output is correct
17 Correct 176 ms 17320 KB Output is correct
18 Correct 118 ms 7092 KB Output is correct
19 Correct 255 ms 27208 KB Output is correct
20 Correct 268 ms 27252 KB Output is correct
21 Correct 255 ms 26964 KB Output is correct
22 Correct 131 ms 16672 KB Output is correct
23 Correct 121 ms 16748 KB Output is correct
24 Correct 130 ms 7012 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -