oj.uz

Submission #100735

# Submission time Handle Problem Language Result Execution time Memory
100735 2019-03-13T20:02:12 Z dalgerok Poklon (COCI17_poklon) C++17
140 / 140
 781 ms 37624 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 14 ms 12160 KB Output is correct
4 Correct 16 ms 12288 KB Output is correct
5 Correct 121 ms 16976 KB Output is correct
6 Correct 133 ms 17072 KB Output is correct
7 Correct 297 ms 22184 KB Output is correct
8 Correct 556 ms 27384 KB Output is correct
9 Correct 663 ms 32576 KB Output is correct
10 Correct 781 ms 37624 KB Output is correct