oj.uz

Submission #744306

# Submission time Handle Problem Language Result Execution time Memory
744306 2023-05-18T11:15:17 Z bgnbvnbv Poklon (COCI17_poklon) C++14
140 / 140
 505 ms 57412 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,bit[maxN];
void update(ll i,ll val)
{
    while(i<=n)
    {
        bit[i]+=val;
        i+=(i&(-i));
    }
}
ll get(ll i)
{
    ll s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=(i&(-i));
    }
    return s;
}
ll q;
ll a[maxN],c[maxN];
vector<ll>vec[maxN];
ll pre[maxN];
vector<pli>quer[maxN];
ll b[maxN];
ll ans[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i],c[i]=a[i];
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+n+1,a[i])-c,vec[a[i]].pb(i),a[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(auto j=1;j<vec[i].size();j++)
        {
            pre[vec[i][j]]=vec[i][j-1];
        }
        if(vec[i].size()>0)
        {
            pre[vec[i][0]]=0;
        }
    }
    for(int i=1;i<=q;i++)
    {
        ll l,r;
        cin >> l >> r;
        quer[r].pb({l,i});
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=b[i]=0;
        ll j=pre[i];
        if(j!=0)
        {
            update(a[j],-1);
            update(b[j]+1,1);
        }
        //j=pre[j];
        //update(pre[j]+1,j,1);
        update(pre[j]+1,1);
        update(j+1,-1);
        a[i]=pre[j]+1;
        b[i]=j;
        for(auto zz:quer[i])
        {
            ans[zz.se]=get(zz.fi);
        }
    }
    //cout << pre[1]<<'\n';
    for(int i=1;i<=q;i++)
    {
        cout << ans[i]<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

poklon.cpp:11:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const ll inf=1e18;
      |              ^~~~
poklon.cpp: In function 'void solve()':
poklon.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(auto j=1;j<vec[i].size();j++)
      |                      ~^~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 13 ms 23888 KB Output is correct
3 Correct 14 ms 23924 KB Output is correct
4 Correct 18 ms 24072 KB Output is correct
5 Correct 78 ms 30192 KB Output is correct
6 Correct 81 ms 30236 KB Output is correct
7 Correct 198 ms 37124 KB Output is correct
8 Correct 281 ms 44452 KB Output is correct
9 Correct 391 ms 51080 KB Output is correct
10 Correct 505 ms 57412 KB Output is correct