(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #748800

#TimeUsernameProblemLanguageResultExecution timeMemory
748800vjudge1Meetings (IOI18_meetings)C++14
100 / 100
3821 ms573772 KiB
#include"meetings.h" #define N 750009 #define LG 20 #define lc(i) ((i)<<1|1) #define rc(i) ((i)+1<<1) #define int long long using namespace std; int n,q,a[N],lg[N],st[LG][N],trek[N<<2],treb[N<<2],lazy[N<<2]; int lft[N<<2],rgt[N<<2]; vector<int>ql[N],qr[N],id[N],ans; inline int qmx(const int&l,const int&r) { int i=lg[r-l]; if(a[st[i][l]]>a[st[i][r-(1<<i)+1]])return st[i][l]; else return st[i][r-(1<<i)+1]; } inline void pd(const int&i,const int&l,const int&r) { if(trek[i]^1<<30) { int mid=l+r>>1; trek[lc(i)]=trek[rc(i)]=trek[i]; treb[lc(i)]=treb[rc(i)]=treb[i]; lazy[lc(i)]=lazy[rc(i)]=0; lft[lc(i)]=trek[i]*l+treb[i]; rgt[lc(i)]=trek[i]*mid+treb[i]; lft[rc(i)]=trek[i]*(mid+1)+treb[i]; rgt[rc(i)]=trek[i]*r+treb[i]; trek[i]=1<<30; } if(lazy[i]) { lazy[lc(i)]+=lazy[i]; lazy[rc(i)]+=lazy[i]; lft[lc(i)]+=lazy[i]; rgt[lc(i)]+=lazy[i]; lft[rc(i)]+=lazy[i]; rgt[rc(i)]+=lazy[i]; lazy[i]=0; } } inline void push(const int&i,const int&l,const int&r,const int&ql, const int&qr,const int&k,const int&b) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr) { trek[i]=k;treb[i]=b;lazy[i]=0; lft[i]=k*l+b; rgt[i]=k*r+b; return; } int mid=l+r>>1;pd(i,l,r); push(lc(i),l,mid,ql,qr,k,b); push(rc(i),mid+1,r,ql,qr,k,b); lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)]; } inline int qry(const int&i,const int&l,const int&r,const int&p) { if(l==r)return lft[i]; int mid=l+r>>1;pd(i,l,r); if(p<=mid)return qry(lc(i),l,mid,p); return qry(rc(i),mid+1,r,p); } inline void add(const int&i,const int&l,const int&r,const int&ql, const int&qr,const int&x) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr){lazy[i]+=x;lft[i]+=x;rgt[i]+=x;return;} int mid=l+r>>1;pd(i,l,r); add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x); lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)]; } inline int find(const int&i,const int&l,const int&r,const int&ql, const int&qr,const int&k,const int&b,const bool&dir) { if(qr<l||r<ql)return-1; if(!dir) { if(qr>=r&&rgt[i]<=k*r+b)return-1; if(ql<=l&&lft[i]>k*l+b)return l; int mid=l+r>>1;pd(i,l,r); int tmp=find(lc(i),l,mid,ql,qr,k,b,0); if(~tmp)return tmp; return find(rc(i),mid+1,r,ql,qr,k,b,0); } else { if(ql<=l&&lft[i]<=k*l+b)return-1; if(qr>=r&&rgt[i]>k*r+b)return r; int mid=l+r>>1;pd(i,l,r); int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1); if(~tmp)return tmp; return find(lc(i),l,mid,ql,qr,k,b,1); } } inline void dfs1(const int&l,const int&r) { if(l==r){push(0,0,n-1,l,l,0,a[l]);return;} int i=qmx(l,r); if(i==l) { dfs1(i+1,r); push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]],a[i]*(qr[i][j]-i+1)); return; } if(i==r) { dfs1(l,i-1); push(0,0,n-1,i,i,0,0); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,ql[i][j])+a[i]); add(0,0,n-1,l,i,a[i]); return; } dfs1(l,i-1);dfs1(i+1,r); push(0,0,n-1,i,i,0,0); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]], qry(0,0,n-1,ql[i][j])+a[i]*(qr[i][j]-i+1)); push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]); add(0,0,n-1,l,i-1,a[i]*(r-i+1)); int k=-a[i],b=qry(0,0,n-1,i)+a[i]*i; int x=find(0,0,n-1,l,i-1,k,b,0); if(~x)push(0,0,n-1,x,i-1,k,b); } inline void dfs2(const int&l,const int&r) { if(l==r){push(0,0,n-1,l,l,0,a[l]);return;} int i=qmx(l,r); if(i==l) { dfs2(i+1,r); push(0,0,n-1,i,i,0,0); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,qr[i][j])+a[i]); add(0,0,n-1,i,r,a[i]); return; } if(i==r) { dfs2(l,i-1); push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]],a[i]*(i-ql[i][j]+1)); return; } dfs2(l,i-1);dfs2(i+1,r); push(0,0,n-1,i,i,0,0); for(int j=0;j<ql[i].size();++j) ans[id[i][j]]=min(ans[id[i][j]], qry(0,0,n-1,qr[i][j])+a[i]*(i-ql[i][j]+1)); push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]); add(0,0,n-1,i+1,r,a[i]*(i-l+1)); int k=a[i],b=qry(0,0,n-1,i)-a[i]*i; int x=find(0,0,n-1,i+1,r,k,b,1); if(~x)push(0,0,n-1,i+1,x,k,b); } vector<int>minimum_costs(vector<signed>H,vector<signed>L,vector<signed>R) { n=H.size();q=L.size();ans.resize(q); for(int i=0;i<n;a[i]=H[i],++i); for(int i=2;i<n;lg[i]=lg[i>>1]+1,++i); for(int i=n-1;i>=0;--i) { st[0][i]=i; for(int j=1;j<LG;++j) if(i+(1<<j-1)<n) if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]]) st[j][i]=st[j-1][i]; else st[j][i]=st[j-1][i+(1<<j-1)]; else st[j][i]=st[j-1][i]; } for(int i=0,u,v,w;i<q;++i) { u=L[i],v=R[i],w=qmx(u,v); if(u==v){ans[i]=a[u];continue;} ql[w].emplace_back(u),qr[w].emplace_back(v), id[w].emplace_back(i);ans[i]=1ll<<60; } for(int i=0;i<N<<2;trek[i++]=1<<30); dfs1(0,n-1); for(int i=0;i<N<<2;trek[i++]=1<<30); dfs2(0,n-1); return ans; }

Compilation message (stderr)

meetings.cpp: In function 'void pd(const long long int&, const long long int&, const long long int&)':
meetings.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid=l+r>>1;
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:22:20: note: in expansion of macro 'rc'
   22 |   trek[lc(i)]=trek[rc(i)]=trek[i];
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:23:20: note: in expansion of macro 'rc'
   23 |   treb[lc(i)]=treb[rc(i)]=treb[i];
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:24:20: note: in expansion of macro 'rc'
   24 |   lazy[lc(i)]=lazy[rc(i)]=0;
      |                    ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:27:7: note: in expansion of macro 'rc'
   27 |   lft[rc(i)]=trek[i]*(mid+1)+treb[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:28:7: note: in expansion of macro 'rc'
   28 |   rgt[rc(i)]=trek[i]*r+treb[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:34:8: note: in expansion of macro 'rc'
   34 |   lazy[rc(i)]+=lazy[i];
      |        ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:37:7: note: in expansion of macro 'rc'
   37 |   lft[rc(i)]+=lazy[i];
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:38:7: note: in expansion of macro 'rc'
   38 |   rgt[rc(i)]+=lazy[i];
      |       ^~
meetings.cpp: In function 'void push(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:55:7: note: in expansion of macro 'rc'
   55 |  push(rc(i),mid+1,r,ql,qr,k,b);
      |       ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:56:31: note: in expansion of macro 'rc'
   56 |  lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
      |                               ^~
meetings.cpp: In function 'long long int qry(const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:63:13: note: in expansion of macro 'rc'
   63 |  return qry(rc(i),mid+1,r,p);
      |             ^~
meetings.cpp: In function 'void add(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;pd(i,l,r);
      |          ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:71:31: note: in expansion of macro 'rc'
   71 |  add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
      |                               ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:72:31: note: in expansion of macro 'rc'
   72 |  lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
      |                               ^~
meetings.cpp: In function 'long long int find(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const bool&)':
meetings.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int mid=l+r>>1;pd(i,l,r);
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:85:15: note: in expansion of macro 'rc'
   85 |   return find(rc(i),mid+1,r,ql,qr,k,b,0);
      |               ^~
meetings.cpp:91:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   int mid=l+r>>1;pd(i,l,r);
      |           ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | #define rc(i) ((i)+1<<1)
      |                ~~~^~
meetings.cpp:92:16: note: in expansion of macro 'rc'
   92 |   int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
      |                ^~
meetings.cpp: In function 'void dfs1(const long long int&, const long long int&)':
meetings.cpp:105:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:113:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:120:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int j=0;j<ql[i].size();++j)
      |              ~^~~~~~~~~~~~~
meetings.cpp: In function 'void dfs2(const long long int&, const long long int&)':
meetings.cpp:137:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:146:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int j=0;j<ql[i].size();++j)
      |               ~^~~~~~~~~~~~~
meetings.cpp:152:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int j=0;j<ql[i].size();++j)
      |              ~^~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:170:14: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  170 |    if(i+(1<<j-1)<n)
      |             ~^~
meetings.cpp:171:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  171 |     if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
      |                                      ~^~
meetings.cpp:173:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  173 |     else st[j][i]=st[j-1][i+(1<<j-1)];
      |                                 ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...