제출 #818224

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

poklon

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define bit(x) (1<<x);
#define getbit(x,pos) ((x<<pos)&1)
#define all(x) x.begin(),x.end()

using namespace std;

template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

const int N=2e5+7;
//const long long p=1e9+7;
const int base=31;
const long long oo =1e18;

typedef pair<int,int> ii;
typedef vector<ii> vii;
int n;
int q;
int a[N];
int s[N];
int idx[N];
int pre[N];
int ans[N];
vector<int>v;
vector<pair<int,int>>queries[N];

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v.pb(a[i]);
    }
    sort(all(v));
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(all(v),a[i]) - v.begin() + 1;
        idx[i] = pre[p];
        pre[p] = i;
    }
    for (int i = 1; i <= q;i++) {
        int u,v;
        cin >> u >> v;
        queries[v].pb(make_pair(u,i));
    }
    for (int r = 1; r <= n; r++) {
        int j = idx[r];
        int i = idx[j];
        int z = idx[i];
        if(j > 0) s[j]++;
        if(i > 0) s[i] -= 2;
        if(z > 0) s[z] ++;
        if((int)queries[r].size() == 0) continue;
        for (int i = 1; i <= r; i++) s[i] = s[i - 1] + s[i];
        for (auto it : queries[r]) {
            int l = it.fi;
            int id = it.se;
            ans[id] = s[r] - s[l - 1];
        }
    }
    for (int i = 1; i <= q; i++) cout << (ans[i] > 0 ? ans[i] : 0) << " ";
    return 0;
}

• Subtask 1: 0 / 140