제출 #818069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
818069		vjudge1	Poklon (COCI17_poklon)	C++17	0 / 140	5080 ms	17088 KiB

poklon

#include <bits/stdc++.h>

using namespace std;
#define N 500007
int n,q,l,r,cnt[N],a[N],dp[N];
vector<pair<int,int>> b;
vector<pair<pair<int,int>,int>> res;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        b.push_back({a[i],i});
    }
    sort(b.begin(),b.end());
    int tmp=0;
    for (int i=0; i<n; i++)
    {
        if(i==0 || b[i].first!=b[i-1].first) tmp++;
        a[b[i].second]=tmp;
    }
    for(int i=1; i<=q; i++)
    {
        cin >> l >> r;
        res.push_back({{l,r},i});
    }
    sort(res.begin(),res.end());
    int l=0,r=0,ans=0;
    for (auto c:res)
    {
        for(int i=r+1;i<=c.first.second; i++)
        {
            cnt[a[i]]++;
            if (cnt[a[i]]>2) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=max(r,c.first.second);
        for (int i=l; i<c.first.first; i++)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
//        cout << ans << "\n";
        l=max(l,c.first.first);
        for (int i=r; i>c.first.second; i--)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=min(r,c.first.second);
        dp[c.second]=ans;
    }
    for(int i=1; i<=q; i++) cout << dp[i] << "\n";
    return 0;
}

• Subtask 1: 0 / 140