Submission #1039493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039493		vjudge1	Meetings (IOI18_meetings)	C++17	17 / 100	56 ms	7380 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
struct segtree{
    int T[1<<18]{};
    void upd(int i,int l,int r,int p,int x){
        if(l==r)return void(T[i]=max(T[i],x));
        if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
        else upd(i*2+1,l+r+2>>1,r,p,x);
        T[i]=max(T[i*2],T[i*2+1]);
    }
    int qry(int i,int l,int r,int ll,int rr){
        if(ll<=l&&r<=rr)return T[i];
        if(l>rr||ll>r) return -1;
        return max(qry(i*2,l,l+r>>1,ll,rr),
                qry(i*2+1,l+r+2>>1,r,ll,rr));
    }
} ST;
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    for(auto&i:R) i++;
    int Q=L.size(),N=H.size();
    H.insert(H.begin(),0);
    vector<long long> C(Q);
    for(auto&i:L) i++;
    vector<int>l(N+2),r(N+2);
    for(int i=1;i<=N;i++)
        l[i]=H[i]-1?0:l[i-1]+1;
    for(int i=N;i;i--)
        r[i]=H[i]-1?0:r[i+1]+1;
    for(int i=1;i<=N;i++)
        ST.upd(1,1,N,i,r[i]+l[i]-1);
    for (int i=0;i<Q;i++) {
        int ll=L[i],rr=R[i],sz=rr-ll+1;
        if(r[ll]>=sz)C[i]=sz;
        else C[i]=2*sz-max({r[ll],l[rr],ST.qry(1,1,N,ll+r[ll],rr-l[rr])});
    }
    return C;
}

Compilation message (stderr)

meetings.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
meetings.cpp:8:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |         if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
      |            ~^~
meetings.cpp:8:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |         if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
      |                                ~^~
meetings.cpp:9:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |         else upd(i*2+1,l+r+2>>1,r,p,x);
      |                        ~~~^~
meetings.cpp: In member function 'int segtree::qry(int, int, int, int, int)':
meetings.cpp:15:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         return max(qry(i*2,l,l+r>>1,ll,rr),
      |                              ~^~
meetings.cpp:16:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |                 qry(i*2+1,l+r+2>>1,r,ll,rr));
      |                           ~~~^~

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