oj.uz

Submission #404759

# Submission time Handle Problem Language Result Execution time Memory
404759 2021-05-14T23:37:31 Z gevacrt Strange Device (APIO19_strange_device) C++17
5 / 100
 5000 ms 301308 KB 
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int A1;

namespace DST {
    struct node {
        int sum{}, lazy{}, tot{};
        node *l = NULL, *r = NULL;
    };
    auto root = new node;

    void upd(node *n, int l, int r){
        if(!n) return;
        if(n->sum) n->tot = r-l+1;
        else{
            n->tot = 0;
            if(n->l) n->tot += n->l->tot;
            if(n->r) n->tot += n->r->tot;
        }
        return;
    }

    void update(node *n, int l, int r, int L, int R, int val){
        if(r < L or R < l) return;

        if(L <= l and r <= R){
            n->sum += val;
            upd(n, l, r);
            return;
        }

        if(!n->l) n->l = new node;
        if(!n->r) n->r = new node;

        int m = (l+r)/2;
        update(n->l, l, m, L, R, val);
        update(n->r, m+1, r, L, R, val);
        upd(n, l, r);
    }

    void update(int L, int R, int val){
        update(root, 0, A1, L, R, val);
    }

    int query(){
        return root->tot;
    }
};

struct rect {
    int x1, y1, x2, y2;
};

int rect_solve(vector<rect> &B){
    ll ans = 0;

    vector<array<int, 4>> q; q.reserve(2*B.size());
    for(auto &i : B){
        q.push_back({i.x2+1, -1, i.y1, i.y2+1});
        q.push_back({i.x1, 1, i.y1, i.y2+1});
    }

    sort(all(q)); int prev_x = 0;
    for(auto &[x, offset, y1, y2] : q){
        ans += ll(x-prev_x)*DST::query();
        prev_x = x;
        DST::update(y1, y2-1, offset);
    }
    return ans;
}

int up(int a, int b){return (a+b-1)/b;}
int down(int a, int b){return a/b;}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int Q, A, B; cin >> Q >> A >> B;
    vector<rect> RC; A1 = A/__gcd(A, B+1);

    RC.reserve(6e6);
    while(Q--){
        int l, r; cin >> l >> r;
        int k1 = up(l, B), k2 = down(r, B);

        auto ins = [&](int x1, int x2, int y1, int y2){
            if(x2-x1+1 >= A1) RC.push_back({0, y1, A1-1, y2});
            else{
                int t1 = x1%A1, t2 = x2%A1;
                if(t1 <= t2) RC.push_back({t1, y1, t2, y2});
                else RC.push_back({t1, y1, A1-1, y2}), RC.push_back({0, y1, t2, y2});
            }
        };

        if(k1 <= k2){
            if(k1 < k2) ins(k1, k2-1, 0, B-1);
            if(l%B != 0) ins(k1-1, k1-1, l%B, B-1);
            ins(k2, k2, 0, r%B);
        }else{
            ins(k2, k2, l%B, r%B);
        }
    }

    cout << rect_solve(RC) << endl;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 11 ms 1356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1378 ms 94280 KB Output is correct
3 Correct 3186 ms 188208 KB Output is correct
4 Correct 3955 ms 188356 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1378 ms 94280 KB Output is correct
3 Correct 3186 ms 188208 KB Output is correct
4 Correct 3955 ms 188356 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4686 ms 282100 KB Output is correct
7 Correct 1380 ms 113440 KB Output is correct
8 Correct 4390 ms 301292 KB Output is correct
9 Execution timed out 5034 ms 301308 KB Time limit exceeded

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1378 ms 94280 KB Output is correct
3 Correct 3186 ms 188208 KB Output is correct
4 Correct 3955 ms 188356 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 209 ms 19120 KB Output is correct
7 Correct 365 ms 28376 KB Output is correct
8 Correct 478 ms 28496 KB Output is correct
9 Correct 556 ms 28496 KB Output is correct
10 Correct 200 ms 16568 KB Output is correct
11 Correct 382 ms 28568 KB Output is correct
12 Correct 497 ms 28620 KB Output is correct
13 Correct 592 ms 28556 KB Output is correct
14 Incorrect 76 ms 9704 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 80 ms 10292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 11 ms 1356 KB Output isn't correct
3 Halted 0 ms 0 KB -