oj.uz

답안 #404758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404758 2021-05-14T23:26:38 Z gevacrt 이상한 기계 (APIO19_strange_device) C++17
25 / 100
 5000 ms 282184 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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; 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; int 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;
}

Compilation message

strange_device.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
strange_device.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 1520 KB Output is correct
3 Correct 26 ms 1784 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 22 ms 1340 KB Output is correct
17 Correct 237 ms 10512 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3603 ms 188220 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2027 ms 94420 KB Output is correct
3 Correct 3765 ms 188184 KB Output is correct
4 Correct 3591 ms 188272 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2027 ms 94420 KB Output is correct
3 Correct 3765 ms 188184 KB Output is correct
4 Correct 3591 ms 188272 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Execution timed out 5111 ms 282136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2027 ms 94420 KB Output is correct
3 Correct 3765 ms 188184 KB Output is correct
4 Correct 3591 ms 188272 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 370 ms 19236 KB Output is correct
7 Correct 578 ms 28492 KB Output is correct
8 Correct 564 ms 28492 KB Output is correct
9 Correct 518 ms 28492 KB Output is correct
10 Correct 334 ms 16776 KB Output is correct
11 Correct 584 ms 28520 KB Output is correct
12 Correct 542 ms 28512 KB Output is correct
13 Correct 584 ms 28484 KB Output is correct
14 Correct 348 ms 38216 KB Output is correct
15 Correct 528 ms 20152 KB Output is correct
16 Correct 401 ms 37264 KB Output is correct
17 Correct 762 ms 56552 KB Output is correct
18 Execution timed out 5083 ms 282184 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 296 ms 20340 KB Output is correct
3 Correct 468 ms 55088 KB Output is correct
4 Execution timed out 5113 ms 238272 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 1520 KB Output is correct
3 Correct 26 ms 1784 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 22 ms 1340 KB Output is correct
17 Correct 237 ms 10512 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 6 ms 588 KB Output is correct
26 Correct 4 ms 716 KB Output is correct
27 Correct 4 ms 460 KB Output is correct
28 Correct 3603 ms 188220 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 2027 ms 94420 KB Output is correct
31 Correct 3765 ms 188184 KB Output is correct
32 Correct 3591 ms 188272 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Execution timed out 5111 ms 282136 KB Time limit exceeded
35 Halted 0 ms 0 KB -