Submission #1174406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174406		ezzzay	Poklon (COCI17_poklon)	C++20	0 / 140	475 ms	21924 KiB

poklon

#include<iostream>
#include<math.h>
#include<utility>
#include<map>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int S = 500;
const int N = 5e5+5;
int arr[N];
map<int,int>cmp;
int cnt=0;
int ans[N];
int val[N];
bool cmp2(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
  if (a.ff.ff / S != b.ff.ff / S) return a.ff.ff< b.ff.ff;
  return (a.ff.ss < b.ff.ss)^(a.ff.ff/S%2);
}
void add(int a){
    val[a]++;
    if(val[a]==2){
        cnt++;
    }
}
void rem(int a){
    val[a]--;
    if(val[a]==1){
        cnt--;
    }
}
signed main(){
    int n,q;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        cmp[arr[i]];
    }
    int k=1;
    for(auto it=cmp.begin() ; it!=cmp.end(); ++it){
        it->ss =  k++;
    }
    for(int i=1;i<=n;i++){
        arr[i] = cmp[arr[i]];
    }
    
    vector<pair<pair<int, int>, int>> qq(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qq[i] = {{l, r}, i};
    }
    sort(qq.begin(), qq.end(), cmp2);
    int L = 0, R = -1;
    for (int i = 0; i < q; i++) {
        int j = qq[i].ss;
        int l = qq[i].ff.ff;
        int r = qq[i].ff.ss;
        while (R < r) add(arr[++R]);
        while (L > l) add(arr[--L]);
        while (R > r) rem(arr[R--]);
        while (L < l) rem(arr[L++]);
        ans[j]=cnt;
       
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<'\n';
    }
}

• Subtask 1: 0 / 140