제출 #1133289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133289		DangKhoizzzz	Poklon (COCI17_poklon)	C++20	140 / 140	670 ms	45324 KiB

poklon

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 5e5 + 7;

int n , q , st[maxn*4] , ans[maxn] , a[maxn];

void update(int id , int l , int r , int pos , int val)
{
    if(l > pos || r < pos) return;
    if(l == r)
    {
        st[id] = val; return;
    }
    int mid = (l+r)/2;
    update(id*2 , l , mid , pos , val);
    update(id*2+1 , mid+1 , r , pos, val);
    st[id] = st[id*2] + st[id*2+1];
}

int getsum(int id , int l , int r , int u , int v)
{
    if(r < u || l > v) return 0;
    if(u <= l && r <= v) return st[id];
    int mid = (l+r)/2;
    return (getsum(id*2 , l , mid , u , v) + getsum(id*2+1 , mid+1 , r , u , v));
}

void compress()
{
    vector <int> val;
    for(int i = 1; i <= n; i++) val.push_back(a[i]);
    sort(val.begin() , val.end());
    for(int i = 1; i <= n; i++)
    {
        a[i] = upper_bound(val.begin() , val.end() , a[i]) - val.begin();
    }
}

vector <int> pos[maxn];
vector <pii> query[maxn];

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    compress();
    for(int i = 1; i <= q; i++)
    {
        int l , r; cin >> l >> r;
        query[r].push_back({l , i});
    }

    for(int i = 1; i <= n; i++)
    {
        pos[a[i]].push_back(i);

        int sz = pos[a[i]].size();

        if(sz >= 2) update(1 , 1 , n , pos[a[i]][sz-2] , 1);
        if(sz >= 3) update(1 , 1 , n , pos[a[i]][sz-3] , -1);
        if(sz >= 4) update(1 , 1 , n , pos[a[i]][sz-4] , 0);


        for(pii tmp: query[i])
        {
            int j = tmp.fi;
            int id = tmp.se;
            ans[id] = getsum(1 , 1 , n , j , i);
        }
    }
    for(int i = 1; i <= q; i++) {cout << ans[i] << '\n';}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 140 / 140