Submission #100735

#	Time	Username	Problem	Language	Result	Execution time	Memory
100735		dalgerok	Poklon (COCI17_poklon)	C++17	140 / 140	781 ms	37624 KiB

poklon

#include<bits/stdc++.h>
using namespace std;


const int N = 5e5 + 5;



int n, m, a[N], ans[N], t[N];
map < int, int > last1, last2, last3;
vector < pair < int, int > > q[N];

inline void upd(int pos, int val){
    for(int i = pos; i <= n; i |= i + 1){
        t[i] += val;
    }
}
inline int get(int pos){
    int cur = 0;
    for(int i = pos; i >= 1; i &= i + 1, i--){
        cur += t[i];
    }
    return cur;
}
inline int get(int l, int r){
    return get(r) - get(l - 1);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        q[r].push_back(make_pair(l, i));
    }
    for(int i = 1; i <= n; i++){
        if(last1.find(a[i]) != last1.end()){
            if(last2.find(a[i]) != last2.end()){
                upd(last2[a[i]], -2);
                if(last3.find(a[i]) != last3.end()){
                    upd(last3[a[i]], +1);
                }
                last3[a[i]] = last2[a[i]];
            }
            last2[a[i]] = last1[a[i]];
            last1[a[i]] = i;
            upd(last2[a[i]], +1);
        }
        else{
            last1[a[i]] = i;
        }
        for(auto it : q[i]){
            ans[it.second] = get(it.first, i);
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 140 / 140