Submission #989664

#	Time	Username	Problem	Language	Result	Execution time	Memory
989664		kasdo	Poklon (COCI17_poklon)	C++14	140 / 140	694 ms	20820 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define speed cin.tie (0) -> sync_with_stdio (0);ios_base::sync_with_stdio(false);cin.tie(0);
#define trace(x) cout << #x << " = " << x << endl
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")
const int maxn = 500005;
const int maxa = 1000005;
int block = sqrt(maxn);
struct query
{
    int l,r,idx;
};
 
bool cmp(query a , query b)
{
    if (a.l / block == b.l / block)
    {
        return a.r < b.r;
    }
    
    return a.l / block < b.l / block;
}
 
int f[maxa] , ans[maxn] , sum;
void add(int x)
{
    if (f[x] == 1) sum++;
    else if (f[x] == 2) sum--;
    f[x]++;
}
void rremove(int x)
{
    if (f[x] == 3) sum++;
    else if (f[x] == 2) sum--;
    f[x]--;
}

signed main()
{
    speed
    
    int n,q;
    cin>>n>>q;
    int a[n+5];
    
    for(int i=0; i<n; i++) cin>>a[i];
    
    query Q[q+5];
    for(int i=0; i<q; i++)
    {
        int l,r;
        cin>>l>>r;
        l--,r--;
        
        Q[i] = {l , r , i};
    }
    
    int ans[q+5] = {};
    sort(Q,Q+q,cmp);
    int l = 0,r = -1;
    for(int i=0; i<q; i++)
    {
        int ll = Q[i].l , rr = Q[i].r , index = Q[i].idx;
        while(l < ll)
        {
            rremove(a[l]);
            l++;
        }
        while(l > ll)
        {
            l--;
            add(a[l]);
        }
        while(r < rr)
        {
            r++;
            add(a[r]);
        }
        while(r > rr)
        {
            rremove(a[r]);
            r--;
        }
        
        ans[index] = sum;
    }
    for(int i=0; i<q; i++) cout<<ans[i]<<endl;
    
    return 0;
}

• Subtask 1: 140 / 140