Submission #816942

#	Time	Username	Problem	Language	Result	Execution time	Memory
816942		Theo830	Poklon (COCI17_poklon)	C++17	140 / 140	1573 ms	37316 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define pb push_back
#define F first
#define S second
const ll siz = 350;
bool comp(iii a,iii b){
    if((a.F.F / siz) == (b.F.F / siz)){
        return a.F.S < b.F.S;
    }
    return (a.F.F / siz) < (b.F.F / siz);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    ll q;
    cin>>q;
    map<ll,ll>mp;
    ll arr[n];
    set<ll>ex;
    f(i,0,n){
        cin>>arr[i];
        ex.insert(arr[i]);
    }
    ll pos = 0;
    for(auto x:ex){
        mp[x] = pos;
        pos++;
    }
    f(i,0,n){
        arr[i] = mp[arr[i]];
    }
    ll siz[n] = {0};
    ll posa[n] = {0};
    ll ans[q];
    vector<iii>ask;
    f(i,0,q){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        ask.pb(iii(ii(a,b),i));
    }
    sort(ask.begin(),ask.end(),comp);
    ll l = 0,r = 0;
    siz[0] = (ll)ex.size() - 1;
    siz[1]++;
    posa[arr[0]]++;
    for(auto x:ask){
        while(l > x.F.F){
            l--;
            posa[arr[l]]++;
            siz[posa[arr[l]]-1]--;
            siz[posa[arr[l]]]++;
        }
        while(r < x.F.S){
            r++;
            posa[arr[r]]++;
            siz[posa[arr[r]]-1]--;
            siz[posa[arr[r]]]++;
        }
        while(l < x.F.F){
            posa[arr[l]]--;
            siz[posa[arr[l]]+1]--;
            siz[posa[arr[l]]]++;
            l++;
        }
        while(r > x.F.S){
            posa[arr[r]]--;
            siz[posa[arr[r]]+1]--;
            siz[posa[arr[r]]]++;
            r--;
        }
        ans[x.S] = siz[2];
    }
    f(i,0,q){
        cout<<ans[i]<<"\n";
    }
}

• Subtask 1: 140 / 140