제출 #744306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744306		bgnbvnbv	Poklon (COCI17_poklon)	C++14	140 / 140	505 ms	57412 KiB

poklon

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 140