oj.uz

Submission #404756

# Submission time Handle Problem Language Result Execution time Memory
404756 2021-05-14T23:18:21 Z gevacrt Strange Device (APIO19_strange_device) C++17
25 / 100
 5000 ms 376124 KB 
#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()

namespace DST {
    struct node {
        int sum{}, lazy{}, tot{};
        unique_ptr<node> l, r;
    };
    auto root = make_unique<node>();

    void upd(unique_ptr<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(unique_ptr<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 = make_unique<node>();
        if(!n->r) n->r = make_unique<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, 1e18+10, 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;
    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; int A1 = A/__gcd(A, B+1);

    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 24 ms 2128 KB Output is correct
3 Correct 26 ms 2128 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 28 ms 2116 KB Output is correct
17 Correct 233 ms 15460 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 844 KB Output is correct
3 Correct 4 ms 844 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 3660 ms 198320 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2121 ms 116600 KB Output is correct
3 Correct 3879 ms 213512 KB Output is correct
4 Correct 3726 ms 213544 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 2121 ms 116600 KB Output is correct
3 Correct 3879 ms 213512 KB Output is correct
4 Correct 3726 ms 213544 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Execution timed out 5086 ms 376124 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2121 ms 116600 KB Output is correct
3 Correct 3879 ms 213512 KB Output is correct
4 Correct 3726 ms 213544 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 387 ms 26760 KB Output is correct
7 Correct 588 ms 46448 KB Output is correct
8 Correct 572 ms 46360 KB Output is correct
9 Correct 548 ms 46384 KB Output is correct
10 Correct 346 ms 26004 KB Output is correct
11 Correct 573 ms 46356 KB Output is correct
12 Correct 575 ms 46360 KB Output is correct
13 Correct 611 ms 46360 KB Output is correct
14 Correct 350 ms 41740 KB Output is correct
15 Correct 541 ms 27000 KB Output is correct
16 Correct 402 ms 41080 KB Output is correct
17 Correct 785 ms 60392 KB Output is correct
18 Execution timed out 5093 ms 376040 KB Time limit exceeded
19 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 Correct 303 ms 24024 KB Output is correct
3 Correct 467 ms 58860 KB Output is correct
4 Execution timed out 5039 ms 253272 KB Time limit exceeded
5 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 Correct 24 ms 2128 KB Output is correct
3 Correct 26 ms 2128 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 28 ms 2116 KB Output is correct
17 Correct 233 ms 15460 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 6 ms 844 KB Output is correct
26 Correct 4 ms 844 KB Output is correct
27 Correct 5 ms 588 KB Output is correct
28 Correct 3660 ms 198320 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 2121 ms 116600 KB Output is correct
31 Correct 3879 ms 213512 KB Output is correct
32 Correct 3726 ms 213544 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Execution timed out 5086 ms 376124 KB Time limit exceeded
35 Halted 0 ms 0 KB -