Submission #1074635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074635		Victor	Meetings (IOI18_meetings)	C++17	0 / 100	35 ms	3284 KiB

meetings

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;

const ll INF = 1'000'000'007;

vll dist;
struct Node {
	ll val,suf,pref,lo,hi;
	Node *l,*r;
	Node(ll L,ll R) : lo(L),hi(R) {
		if(hi-lo==1) {
			if(dist[lo]==1)	val=suf=pref=1;
			else val=suf=pref=0;
		}

		else {
			ll mid=(lo+hi)/2;
			l=new Node(lo,mid);
			r=new Node(mid,hi);
			auto item=comb({l->val,{l->pref,l->suf}},{r->val,{r->pref,r->suf}});
			val=item.first;
			pref=item.second.first;
			suf=item.second.second;
		}
	}

	ppll query(ll L,ll R) {
		if(R<=lo||hi<=L) return {0,{0,0}};
		if(L<=lo&&hi<=R) return {val,{pref,suf}};


		auto a= comb(l->query(L,R),r->query(L,R));
		//cout<<"lo = "<<lo<<" hi = "<<hi<<" val = "<<a.first<<" pref = "<<a.second.first<<" suf = "<<a.second.second<<endl;
		return a;
	}

	ppll comb(ppll a,ppll b) {
		ll curval,cursuf,curpref;
		curval=max(a.first,b.first);
		cursuf=b.second.second;
		curpref=a.second.first;

		if(a.first==l->hi-l->lo) curpref=a.first+b.second.first;
		if(b.first==r->hi-r->lo) cursuf=b.first+a.second.second;

		return {curval,{cursuf,curpref}};
	}
};

ll n,q;

vll minimum_costs(vi H, vi L, vi R) {
	n=sz(H);
	q=sz(L);
	vll answers(q);

	ll pos=-1;
	dist.assign(n,-1);
	rep(i,0,n) dist[i]=H[i];

	Node segtree(0,n);
	rep(i,0,q) {
		//cout<<"i = "<<i<<' '<<segtree.query(L[i],R[i]+1).first<<endl;
		answers[i]=(R[i]-L[i]+1)*2-segtree.query(L[i],R[i]+1).first;
	}
	return answers;
}

/**
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}/**/

Compilation message (stderr)

meetings.cpp:131:2: warning: "/*" within comment [-Wcomment]
  131 | }/**/
      |   
meetings.cpp: In function 'vll minimum_costs(vi, vi, vi)':
meetings.cpp:87:5: warning: unused variable 'pos' [-Wunused-variable]
   87 |  ll pos=-1;
      |     ^~~

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