oj.uz

Submission #816942

# Submission time Handle Problem Language Result Execution time Memory
816942 2023-08-09T07:38:57 Z Theo830 Poklon (COCI17_poklon) C++17
140 / 140
 1573 ms 37316 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 792 KB Output is correct
5 Correct 121 ms 7928 KB Output is correct
6 Correct 117 ms 7872 KB Output is correct
7 Correct 294 ms 15420 KB Output is correct
8 Correct 618 ms 26916 KB Output is correct
9 Correct 1002 ms 30468 KB Output is correct
10 Correct 1573 ms 37316 KB Output is correct