oj.uz

답안 #404760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404760 2021-05-14T23:39:47 Z gevacrt 이상한 기계 (APIO19_strange_device) C++17
5 / 100
 5000 ms 282184 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+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; 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1327 ms 94372 KB Output is correct
3 Correct 3168 ms 188200 KB Output is correct
4 Correct 3933 ms 188176 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1327 ms 94372 KB Output is correct
3 Correct 3168 ms 188200 KB Output is correct
4 Correct 3933 ms 188176 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4707 ms 282096 KB Output is correct
7 Correct 1392 ms 94404 KB Output is correct
8 Correct 4385 ms 282184 KB Output is correct
9 Execution timed out 5090 ms 282140 KB Time limit exceeded

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1327 ms 94372 KB Output is correct
3 Correct 3168 ms 188200 KB Output is correct
4 Correct 3933 ms 188176 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 210 ms 19132 KB Output is correct
7 Correct 373 ms 28484 KB Output is correct
8 Correct 496 ms 28532 KB Output is correct
9 Correct 544 ms 28496 KB Output is correct
10 Correct 197 ms 16572 KB Output is correct
11 Correct 355 ms 28496 KB Output is correct
12 Correct 471 ms 28412 KB Output is correct
13 Correct 599 ms 28540 KB Output is correct
14 Incorrect 76 ms 9668 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 80 ms 10296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 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 -