oj.uz

Submission #820204

# Submission time Handle Problem Language Result Execution time Memory
820204 2023-08-11T01:13:12 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 647 ms 59780 KB 
#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()
#define int long long
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=5e5+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 aa[N];
int idx[N];
int pre[N];
int ans[N];
vector<int>v;
vector<pair<int,int>>queries[N];

struct segnode
{
    long long val;
    segnode (long long _val=0)
    {
        val=_val;
    }
    segnode operator + (segnode a)
    {
        return segnode(val+a.val);
    }
};

struct segtree
{
    int n;
    segnode tree[4*N];
    segtree(){};
    void init (int _n=0)
    {
        n=_n;
    }
    void update(int id, int l, int r, int u, int v, int x)
    {
        if (v<l || r<u) return ;
        if (l>=u && r<=v)
        {
            tree[id].val+=x;
            return;
        }
        int m=(l+r)>>1;
        update(id*2,l,m,u,v,x);
        update(id*2+1,m+1,r,u,v,x);
        tree[id]=tree[id*2]+tree[id*2+1];
    }
    segnode get(int id, int l, int r, int u, int v)
    {
        if (v<l || r<u ) return segnode();
        if (l>=u && r<=v)
        {
            return tree[id];
        }
        int m=(l+r)>>1;
        return get(id*2,l,m,u,v)+get(id*2+1,m+1,r,u,v);
    }
}it;
signed 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));
    it.init(n);
    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)
        {
//            aa[j]++;
//            int tmp=aa[j];
            it.update(1,1,n,j,j,1);
        }
        if(i > 0)
        {
//            aa[i] -= 2;
//            int tmp=aa[i];
            it.update(1,1,n,i,i,-2);
        }
        if(z > 0)
        {
//            aa[z] ++;
//            int tmp=aa[z];
            it.update(1,1,n,z,z,1);
        }
        //for (int i = 1; i <= r; i++) s[i] = s[i - 1] + aa[i];
        for (auto itt : queries[r])
        {
            int l = itt.fi;
            int id = itt.se;
            ans[id] = it.get(1,1,n,l,r).val;
        }
    }
    for (int i = 1; i <= q; i++) cout << (ans[i] > 0 ? ans[i] : 0) << "\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27744 KB Output is correct
2 Correct 11 ms 27692 KB Output is correct
3 Correct 12 ms 27732 KB Output is correct
4 Correct 15 ms 28096 KB Output is correct
5 Correct 104 ms 33824 KB Output is correct
6 Correct 102 ms 34040 KB Output is correct
7 Correct 231 ms 41124 KB Output is correct
8 Correct 365 ms 47976 KB Output is correct
9 Correct 498 ms 53928 KB Output is correct
10 Correct 647 ms 59780 KB Output is correct