제출 #818086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
818086		vjudge1	Poklon (COCI17_poklon)	C++14	84 / 140	5056 ms	17188 KiB

poklon

#include <bits/stdc++.h>

using namespace std;
#define N 1000007
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=1;
    a[b[0].second]=tmp;
    for (int i=1; i<n; i++)
    {
        if(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 (int j=0; j<q; j++)
    {
//        cout << c.first.first << " " << c.first.second <<"\n";
        for(int i=r+1;i<=res[j].first.second; i++)
        {
            cnt[a[i]]++;
            if (cnt[a[i]]==3) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=max(r,res[j].first.second);
//        cout << ans << "\n";
        for (int i=l; i<res[j].first.first; i++)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        l=max(l,res[j].first.first);
//        cout << ans << "\n";
        for (int i=r; i>res[j].first.second; i--)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=min(r,res[j].first.second);
//        cout << ans << "\n";
        dp[res[j].second]=ans;
    }
    for(int i=1; i<=q; i++) cout << dp[i] << "\n";
    return 0;
}

• Subtask 1: 84 / 140