oj.uz

Submission #555744

# Submission time Handle Problem Language Result Execution time Memory
555744 2022-05-01T12:42:07 Z MohamedFaresNebili Poklon (COCI17_poklon) C++14
140 / 140
 2139 ms 16464 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        /// #define int ll

        const int oo = 1e9 + 7;
        const int batch = 514;

        int N, Q, arr[500001], occ[500001], res[500001];
        vector<array<int, 3>> query; vector<int> curr;
        bool cmp(array<int, 3> A, array<int, 3> B) {
            if(A[0] / batch != B[0] / batch)
                return A[0] / batch < B[0] / batch;
            return A[1] < B[1];
        }

		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> Q;
            for(int l = 0; l < N; l++) {
                cin >> arr[l]; curr.pb(arr[l]);
            }
            for(int l = 0; l < Q; l++) {
                int lf, rf; cin >> lf >> rf;
                lf--; rf--; query.pb({lf, rf, l});
            }
            sort(all(curr)); sort(all(query), cmp);
            for(int l = 0; l < N; l++)
                arr[l] = lb(all(curr), arr[l]) - curr.begin();
            int ans = 0, lo = 0, hi = -1;
            for(int i = 0; i < Q; i++) {
                int l = query[i][0], r = query[i][1], j = query[i][2];
                while(lo > l) {
                    lo--; int v = arr[lo];
                    if(occ[v] == 2) ans--;
                    occ[v]++;
                    if(occ[v] == 2) ans++;
                }
                while(hi < r) {
                    hi++; int v = arr[hi];
                    if(occ[v] == 2) ans--;
                    occ[v]++;
                    if(occ[v] == 2) ans++;
                }
                while(lo < l) {
                    int v = arr[lo];
                    if(occ[v] == 2) ans--;
                    occ[v]--;
                    if(occ[v] == 2) ans++;
                    lo++;
                }
                while(hi > r) {
                    int v = arr[hi];
                    if(occ[v] == 2) ans--;
                    occ[v]--;
                    if(occ[v] == 2) ans++;
                    hi--; 
                }
                res[j] = ans;
            }
            for(int l = 0; l < Q; l++) cout << res[l] << "\n";
		}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 157 ms 3404 KB Output is correct
6 Correct 165 ms 3596 KB Output is correct
7 Correct 520 ms 6972 KB Output is correct
8 Correct 919 ms 10676 KB Output is correct
9 Correct 1460 ms 13604 KB Output is correct
10 Correct 2139 ms 16464 KB Output is correct