oj.uz

답안 #398386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398386 2021-05-04T08:23:38 Z AKiko 이상한 기계 (APIO19_strange_device) C++17
0 / 100
 3432 ms 369500 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ss second
#define ff first
#define pb push_back
#define pii pair<int, int>
#define INF INT_MAX
#define debug(n) cout << #n << " = " << n << "\n";
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll MOD = 1e9 + 7;

int main() {
    ll n, A, B;
    cin >> n >> A >> B;
    unordered_map<ll, vector<pair<ll, ll> > > umap;
    map<ll, ll> fullset;
    ll L = 0;
    for(int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        L += r - l + 1;
        if(l / B != r / B) {
            // cout << (l / B) << " " << (r / B) << " these values are inserted\n";
            umap[(l / B)].pb({l % B, B - 1});
            umap[(r / B)].pb({0, r % B});
        } else {
            umap[(l / B)].pb({l % B, r % B});
            // cout << (l / B) << " inserted\n";
        }
        fullset[l / B + 1]++;
        fullset[r / B]--;
    }
    ll prev = 0;
    vector<pair<ll, ll > > fset;
    for(auto el : fullset) {
        prev += el.ss;
        // cout << el.ff << " " << el.ss << " fset" << "\n";
        fset.pb({el.ff, prev});
    }
    // for(auto el : fset) {
    //     cout << el.ff << " " << el.ss << "\n";
    // }
    map<ll, ll> fs;

    // cut
    for(int i = 0; i < int(fset.size() - 1); i++) {
        if(fset[i].ff / A != fset[i + 1].ff / A) {
            fs[fset[i].ff % A] += fset[i].ss;
            fs[A] -= fset[i].ss; 
            fs[0] += fset[i].ss;
            fs[fset[i + 1].ff % A] -= fset[i].ss;
            fs[0] += (fset[i + 1].ff / A - fset[i].ff / A - 1);
            fs[A] -= (fset[i + 1].ff / A - fset[i].ff / A - 1);
        } else {
            fs[fset[i].ff % A] += fset[i].ss;
            fs[fset[i + 1].ff % A] -= fset[i].ss;
        }
    }
    prev = 0;
    vector<pair<ll, ll> > nfset;
    for(auto el : fs) {
        // cout << el.ff << " " << el.ss << " fs elements\n";
        prev += el.ss;
        nfset.pb({el.ff, prev});
    }
    // debug(L);
    if(nfset.size() > 0) {
        for(int i = 1; i < int(nfset.size()); i++) {
            // cout << nfset[i - 1].ff << " " << nfset[i].ff << " segment have " << nfset[i - 1].ss << " elements wtf ? \n";
            L -= (nfset[i].ff - nfset[i - 1].ff) * max(nfset[i - 1].ss - 1, 0LL);
            nfset[i - 1].ss = min(nfset[i - 1].ss, 1LL);
        }
        nfset.back().ss = min(nfset.back().ss, 1LL); // ? 
    }
    // debug(L);


    unordered_map<ll, bool> calculated;
    unordered_map<ll, vector<pair<ll, ll> > > umapmod;

    for(auto el : umap) {
        for(auto x : el.ss)
            umapmod[el.ff % A].pb(x);
    }

    for(auto el : umap) {
        if(calculated[el.ff % A] == 1) {
            continue;
        }
        // cout << el.ff << " first \n";
        vector<pair<ll, ll> > segments = umapmod[el.ff % A];
        // for(auto e : segments) {
        //     cout << e.ff << " " << e.ss << " seg\n";
        // }
        pair<ll, ll> f = {el.ff % A, INT64_MAX};
        // cout << "index : " << int(upper_bound(fset.begin(), fset.end(), f) - fset.begin()) - 1 << "\n";
        int ind = int(upper_bound(nfset.begin(), nfset.end(), f) - nfset.begin()) - 1;
        ll full = (ind >= 0 ? nfset[ind].ss : 0);
        map<ll, ll> m;
        for(auto seg : segments) {
            m[seg.ff]++;
            m[seg.ss + 1]--;
        }
        prev = 0;
        vector<pair<ll, ll> > line;
        for(auto e : m) {
            prev += e.ss;
            line.pb({e.ff, prev});
        }
        // debug(full);
        // cout << "--------------------------\ncalculating .. \n";
        for(int i = 1; i < int(line.size()); i++) {
            ll cnt = line[i].ff - line[i - 1].ff;
            // cout << line[i - 1].ff << " " << line[i].ff << " this segment have " << line[i - 1].ss - 1 + full << " multiple elements\n";
            L -= cnt * max(line[i - 1].ss - 1 + full, 0LL);
        }
        // cout << "done .. L = " << L << "\n";
        calculated[el.ff % A] = 1;
    }
    cout << L << "\n";



    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 19 ms 960 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 208 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 Incorrect 4 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 197 ms 4340 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 19 ms 960 KB Output isn't correct
3 Halted 0 ms 0 KB -