Submission #398334

#	Time	Username	Problem	Language	Result	Execution time	Memory
398334		AKiko	Strange Device (APIO19_strange_device)	C++17	0 / 100	1 ms	204 KiB

strange_device

#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;
        fset.pb({el.ff, prev});
    }
    map<ll, ll> fs;

    // cut
    for(int i = 0; i < 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 : fset) {
        prev += el.ss;
        nfset.pb({el.ff, prev});
    }
    // debug(L);
    if(nfset.size() > 0) {
        for(int i = 1; i < 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) * A;
            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 ? fset[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});
        }
        // cout << "--------------------------\ncalculating .. \n";
        for(int i = 1; i < 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
*/

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < fset.size() - 1; i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
strange_device.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i = 1; i < nfset.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
strange_device.cpp:91:18: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   91 |         for(auto e : segments) {
      |                  ^
strange_device.cpp:110:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int i = 1; i < line.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30