oj.uz

Submission #109141

# Submission time Handle Problem Language Result Execution time Memory
109141 2019-05-04T16:52:26 Z Frankenween Poklon (COCI17_poklon) C++17
140 / 140
 1420 ms 37340 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod1 = (ll)1e9 + 7;
const ll mod2 = (ll)1e9 + 9;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct seg {
    ll l, r, i;
};


void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> arr(n);
    cin >> arr;
    vector<ll> sarr = arr;
    sort(all(sarr));
    map<ll, ll> new_ind;
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 or sarr[i] != sarr[i - 1]) {
            new_ind[sarr[i]] = cnt;
            cnt++;
        }
    }
    for (int i = 0; i < n; i++) {
        arr[i] = new_ind[arr[i]];
    }
    vector<seg> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--;
        queries[i].r--;
        queries[i].i = i;
    }
    ll K = sqrt(n) + 1;
    sort(all(queries), [&](seg a, seg b) {
        if (a.l / K != b.l / K) {
            return a.l / K < b.l / K;
        }
        return a.r < b.r;
    });
    vector<ll> have(n), res(q);
    ll ans = 0;
    ll l = 0, r = -1;
    for (int i = 0; i < q; i++) {
        while (r < queries[i].r) {
            r++;
            have[arr[r]]++;
            if (have[arr[r]] == 2) {
                ans++;
            }
            if (have[arr[r]] == 3) {
                ans--;
            }
        }
        while (l > queries[i].l) {
            l--;
            have[arr[l]]++;
            if (have[arr[l]] == 2) {
                ans++;
            }
            if (have[arr[l]] == 3) {
                ans--;
            }
        }
        while (r > queries[i].r) {
            have[arr[r]]--;
            if (have[arr[r]] == 1) {
                ans--;
            }
            if (have[arr[r]] == 2) {
                ans++;
            }
            r--;
        }
        while (l < queries[i].l) {
            have[arr[l]]--;
            if (have[arr[l]] == 1) {
                ans--;
            }
            if (have[arr[l]] == 2) {
                ans++;
            }
            l++;
        }
        res[queries[i].i] = ans;
    }
    for (auto i : res) {
        cout << i << "\n";
    }
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 153 ms 7544 KB Output is correct
6 Correct 157 ms 7644 KB Output is correct
7 Correct 418 ms 15112 KB Output is correct
8 Correct 765 ms 22584 KB Output is correct
9 Correct 1084 ms 30056 KB Output is correct
10 Correct 1420 ms 37340 KB Output is correct