oj.uz

Submission #989664

# Submission time Handle Problem Language Result Execution time Memory
989664 2024-05-28T13:51:22 Z kasdo Poklon (COCI17_poklon) C++14
140 / 140
 694 ms 20820 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 77 ms 4368 KB Output is correct
6 Correct 79 ms 4352 KB Output is correct
7 Correct 195 ms 8528 KB Output is correct
8 Correct 351 ms 12628 KB Output is correct
9 Correct 512 ms 16988 KB Output is correct
10 Correct 694 ms 20820 KB Output is correct