Submission #741695

#	Time	Username	Problem	Language	Result	Execution time	Memory
741695		myrcella	Meetings (IOI18_meetings)	C++17	17 / 100	89 ms	9396 KiB

meetings

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "meetings.h"
 
const int maxn = 1e5+10;
pair<int,pii> tree[maxn*4];
int h[maxn];
int n;
 
pair<int,pii> merge(pair<int,pii> a,pair<int,pii> b,int lsz,int rsz) {
	pair<int,pii> ret;
	ret.se.fi = a.se.fi;
	if (a.se.fi==lsz) ret.se.fi += b.se.fi;
	ret.se.se = b.se.se;
	if (b.se.se==rsz) ret.se.se += a.se.se;
	ret.fi = max(a.fi,b.fi);
	ret.fi = max(ret.fi,a.se.se+b.se.fi);
	return ret;
}
 
void init(int c,int cl,int cr) {
	if (cl==cr) {
		int tmp = (h[cl]==1);
		tree[c] = {tmp,{tmp,tmp}};
		return;
	}
	int mid=cl+cr>>1;
	init(c<<1,cl,mid);
	init(c<<1|1,mid+1,cr);
	tree[c] = merge(tree[c<<1],tree[c<<1|1],mid-cl+1,cr-mid);
}
 
pair <int,pii> query(int c,int cl,int cr,int l,int r) {
	if (l<=cl and cr<=r) return tree[c];
	int mid=cl+cr>>1;
	if (l<=mid and r<=mid) return query(c<<1,cl,mid,l,r);
	if (r>mid and l>mid) return query(c<<1|1,mid+1,cr,l,r);
	return merge(query(c<<1,cl,mid,l,r),query(c<<1|1,mid+1,cr,l,r),mid-max(l,cl)+1,min(cr,r)-mid);
}
 
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C;
  n = SZ(H);
  rep(i,0,n) h[i] = H[i];
  init(1,0,n-1);
  rep(i,0,SZ(L)) {
	  pair<int,pii> tmp = query(1,0,n-1,L[i],R[i]);
	  int ans = (R[i]-L[i]+1)*2 - max(tmp.fi,max(tmp.se.fi,tmp.se.se));
	  C.pb(ans);
  }
  return C;
}

Compilation message (stderr)

meetings.cpp: In function 'void init(int, int, int)':
meetings.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |  int mid=cl+cr>>1;
      |          ~~^~~
meetings.cpp: In function 'std::pair<int, std::pair<int, int> > query(int, int, int, int, int)':
meetings.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid=cl+cr>>1;
      |          ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:64:7: warning: unused variable 'Q' [-Wunused-variable]
   64 |   int Q = L.size();
      |       ^

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