oj.uz

Submission #519047

# Submission time Handle Problem Language Result Execution time Memory
519047 2022-01-25T13:15:35 Z ac2hu Poklon (COCI17_poklon) C++14
140 / 140
 1220 ms 19492 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int block = 400;
int a[N];
int freq[N];
int ans[N];
struct queries{
    int i,l,r;
} qq[N];
int n,q;
int temp = 0;
inline void add(int i){
    if(freq[a[i]] == 2)
        temp--;
    freq[a[i]]++;
    if(freq[a[i]] == 2)
        temp++;
}
inline void remove(int i){
    if(freq[a[i]] == 2)
        temp--;
    freq[a[i]]--;
    if(freq[a[i]] == 2)
        temp++;
}
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
    cin >> n >> q;
    for(int i = 0;i<n;i++)cin >> a[i];
    for(int i = 0;i<q;i++){
        cin >> qq[i].l >> qq[i].r;
        qq[i].l--;
        qq[i].r--;
        qq[i].i = i;
    }
    sort(qq,qq + q,[&](queries a,queries b){
        int ab = a.l/block;
        int bb = b.l/block;
        if(ab == bb){
            if(ab%2 == 0)
                return a.r < b.r;
            else
                return a.r > b.r;
        }
        else 
            return ab < bb;
    });
    int l = 0,r = -1;
    for(int i = 0;i<q;i++){
        while(r < qq[i].r){
            r++;
            add(r);
        }
        while(l > qq[i].l){
            l--;
            add(l);
        }
        while(r > qq[i].r){
            remove(r);
            r--;
        }
        while(l < qq[i].l){
            remove(l);
            l++;
        }
        ans[qq[i].i] = temp;
    }
    for(int i = 0;i<q;i++)
        cout << ans[i] << "\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 4 ms 448 KB Output is correct
5 Correct 105 ms 3836 KB Output is correct
6 Correct 112 ms 3844 KB Output is correct
7 Correct 290 ms 7816 KB Output is correct
8 Correct 558 ms 11736 KB Output is correct
9 Correct 853 ms 15656 KB Output is correct
10 Correct 1220 ms 19492 KB Output is correct