Submission #719762

#	Time	Username	Problem	Language	Result	Execution time	Memory
719762		bin9638	Meetings (IOI18_meetings)	C++17	17 / 100	85 ms	9532 KiB

meetings

#include <bits/stdc++.h>

#ifndef SKY
#include "meetings.h"
#endif // SKY

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n,q,nxt[N],pre[N];
ll a[N];

struct IT
{
    int ST[N*4]={};

    void update(int id,int l,int r,int i,int val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=max(ST[id*2],ST[id*2+1]);
    }

    int get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return 0;
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}T;

struct truyvan
{
    int l,r,id;
    bool operator<(const truyvan&A)const
    {
        return l<A.l;
    }
}tv[N];

vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R)
{
    n=H.size();
    for(int i=0;i<n;i++)
        a[i]=H[i]-1;//,assert(a[i]>=1&&a[i]<=2);
    q=L.size();
    vector<ll>kq(q);
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<n+100;i++)
        nxt[i]=n;
    //cout<<n<<" "<<q<<endl;
    for(int i=0;i<n;i++)
        if(a[i]==1)
            pre[i]=i;
                else{
                    if(i>0)
                        pre[i]=pre[i-1];
                }
    for(int i=n-1;i>=0;i--)
        if(a[i]==1)
            nxt[i]=i;
                else nxt[i]=nxt[i+1];
    for(int i=0;i<n;i++)
        if(a[i]==0&&pre[i]==i-1)
            T.update(1,1,n,min(n-1,nxt[i]-1),min(n-1,nxt[i]-1)-i+1);//,cout<<i<<endl;
    for(int i=0;i<q;i++)
        tv[i]={L[i],R[i],i};
    sort(tv,tv+q);
    for(int pos=0,t=0;t<q;t++)
    {
        int l=tv[t].l,r=tv[t].r;
        while(pos<l)
        {
            if(a[pos]==0&pre[pos]==pos-1)
                T.update(1,1,n,min(n-1,nxt[pos]-1),0);
            pos++;
        }
        int res=max(0,T.get(1,1,n,l,r));
        if(a[l]==0)
            res=max(res,min(r,nxt[l]-1)-max(l,pre[l]+1)+1);
        if(a[r]==0)
             res=max(res,min(r,nxt[r]-1)-max(l,pre[r]+1)+1);
       // cout<<l<<" "<<r<<" "<<res<<endl;
        kq[tv[t].id]=(r-l+1)*2-res;
    }
    return kq;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    vector<int>H(n),L(q),R(q);
    for(int i=0;i<n;i++)
        cin>>H[i];
    for(int i=0;i<q;i++)
        cin>>L[i]>>R[i];
    vector<ll>kq=minimum_costs(H,L,R);
    for(int i=0;i<q;i++)cout<<kq[i]<<endl;
    return 0;
}
#endif

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:91:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   91 |             if(a[pos]==0&pre[pos]==pos-1)
      |                ~~~~~~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40