제출 #555742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555742		MohamedFaresNebili	Poklon (COCI17_poklon)	C++14	28 / 140	2076 ms	24972 KiB

poklon

#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) {
                    hi--; int v = arr[hi];
                    if(occ[v] == 2) ans--;
                    occ[v]--;
                    if(occ[v] == 2) ans++;
                }
                res[j] = ans;
            }
            for(int l = 0; l < Q; l++) cout << res[l] << "\n";
		}

• Subtask 1: 28 / 140