oj.uz

답안 #707584

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707584 2023-03-09T11:52:23 Z AdamGS 모임들 (IOI18_meetings) C++17
100 / 100
 5308 ms 222980 KB 
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=75e4+7;
vector<pair<pair<int,int>,int>>V[LIM];
pair<ll,ll>tr[4*LIM][2], pytanie[4*LIM], T[LIM], zle={-1, -1};
set<pair<int,int>>S;
ll dodaj[4*LIM][2], ile[4*LIM], N=1;
void spl(int v, int k) {
	if(tr[v][k]!=zle) {
		tr[2*v][k]=tr[v][k];
		tr[2*v+1][k]={tr[v][k].st+ile[2*v]*tr[v][k].nd, tr[v][k].nd};
		tr[v][k]=zle;
		dodaj[2*v][k]=0;
		dodaj[2*v+1][k]=0;
	}
	if(dodaj[v][k]) {
		if(tr[2*v][k]!=zle) tr[2*v][k].st+=dodaj[v][k];
		else dodaj[2*v][k]+=dodaj[v][k];
		if(tr[2*v+1][k]!=zle) tr[2*v+1][k].st+=dodaj[v][k];
		else dodaj[2*v+1][k]+=dodaj[v][k];
		dodaj[v][k]=0;
	}
}
void updd(int v, int l, int r, int a, int b, ll x, int k) {
	if(r<a || l>b) return;
	if(a<=l && r<=b) {
		if(tr[v][k]==zle) dodaj[v][k]+=x;
		else tr[v][k].st+=x;
		return;
	}
	spl(v, k);
	int mid=(l+r)/2;
	updd(2*v, l, mid, a, b, x, k);
	updd(2*v+1, mid+1, r, a, b, x, k);
}
void upds(int v, ll l, ll r, int a, int b, ll x, ll y, int k) {
	if(r<a || l>b) return;
	if(a<=l && r<=b) {
		dodaj[v][k]=0;
		tr[v][k]={x+y*l, y};
		return;
	}
	spl(v, k);
	int mid=(l+r)/2;
	upds(2*v, l, mid, a, b, x, y, k);
	upds(2*v+1, mid+1, r, a, b, x, y, k);
}
ll pytaj(ll v, int l, int r, int x, int k) {
	if(l==r) return tr[v][k].st;
	spl(v, k);
	int mid=(l+r)/2;
	if(x<=mid) return pytaj(2*v, l, mid, x, k);
	return pytaj(2*v+1, mid+1, r, x, k);
}
pair<ll,ll>jakie(int l, int r) {
	l+=N; r+=N;
	pair<ll,ll>ans=max(pytanie[l], pytanie[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, pytanie[l+1]);
		if(r%2==1) ans=max(ans, pytanie[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
vector<ll>minimum_costs(vector<int>H, vector<int>L, vector<int>R) { 
	int n=H.size();
	while(N<=n) N*=2;
	rep(i, N) ile[N+i]=1;
	for(int i=N-1; i; --i) ile[i]=ile[2*i]+ile[2*i+1];
	rep(i, n) {
		T[i]={H[i], i};
		pytanie[N+i]={H[i], i};
	}
	for(int i=N-1; i; --i) pytanie[i]=max(pytanie[2*i], pytanie[2*i+1]);
	rep(i, L.size()) V[jakie(L[i], R[i]).nd].pb({{L[i], R[i]}, i});
	vector<ll>wyniki(L.size());
	sort(T, T+n);
	S.insert({-LIM, -LIM});
	S.insert({LIM, LIM});
	rep(i, n) {
		for(auto j : V[T[i].nd]) {
			wyniki[j.nd]=pytaj(1, 0, N-1, j.st.nd, 0)+(T[i].nd-j.st.st+1)*T[i].st;
			wyniki[j.nd]=min(wyniki[j.nd], pytaj(1, 0, N-1, n-j.st.st, 1)+(j.st.nd-T[i].nd+1)*T[i].st);
		}
		auto it=S.lower_bound({T[i].nd, T[i].nd});
		auto prawo=*it; --it;
		auto lewo=*it;
		pair<ll,ll>lewod={T[i].nd, T[i].nd}, prawod={T[i].nd, T[i].nd};
		if(lewo.nd==T[i].nd-1) {
			S.erase(lewo);
			lewod.st=lewo.st;
		}
		if(prawo.st==T[i].nd+1) {
			S.erase(prawo);
			prawod.nd=prawo.nd;
		}
		updd(1, 0, N-1, prawod.st, prawod.nd, T[i].st*(lewod.nd-lewod.st+1), 0);
		// znajduje ostatni element na ktorym dp[T[i].nd-1]+(po-T[i].nd+1)*T[i].st<pytaj(po)
		ll dplewo=0, po=prawod.st, ko=prawod.nd;
		if(lewod.st!=T[i].nd) dplewo=pytaj(1, 0, N-1, T[i].nd-1, 0);
		while(po<ko) {
			ll sr=(po+ko+1)/2;
			if(dplewo+(sr-T[i].nd+1)*T[i].st<=pytaj(1, 0, N-1, sr, 0)) po=sr; else ko=sr-1;
		}
		upds(1, 0, N-1, T[i].nd, po, dplewo+(1-T[i].nd)*T[i].st, T[i].st, 0);
		updd(1, 0, N-1, n-lewod.nd, n-lewod.st, T[i].st*(prawod.nd-prawod.st+1), 1);
		// znajduje pierwszy element na ktorym dpprawo+(T[i].nd-sr+1)*T[i].st<pytaj(sr)
		ll dpprawo=0; po=lewod.st; ko=lewod.nd;
		if(prawod.st!=prawod.nd) dpprawo=pytaj(1, 0, N-1, n-T[i].nd-1, 1);
		while(po<ko) {
			ll sr=(po+ko)/2;
			if(dpprawo+(T[i].nd-sr+1)*T[i].st<=pytaj(1, 0, N-1, n-sr, 1)) ko=sr; else po=sr+1;
		}
		upds(1, 0, N-1, n-T[i].nd, n-po, dpprawo+(T[i].nd+1-n)*T[i].st, T[i].st, 1);
		S.insert({lewod.st, prawod.nd});
	}
	return wyniki;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
meetings.cpp:83:2: note: in expansion of macro 'rep'
   83 |  rep(i, L.size()) V[jakie(L[i], R[i]).nd].pb({{L[i], R[i]}, i});
      |  ^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 16 ms 18456 KB Output is correct
3 Correct 14 ms 18456 KB Output is correct
4 Correct 15 ms 18484 KB Output is correct
5 Correct 16 ms 18516 KB Output is correct
6 Correct 16 ms 18516 KB Output is correct
7 Correct 15 ms 18516 KB Output is correct
8 Correct 16 ms 18516 KB Output is correct
9 Correct 16 ms 18516 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 16 ms 18456 KB Output is correct
3 Correct 14 ms 18456 KB Output is correct
4 Correct 15 ms 18484 KB Output is correct
5 Correct 16 ms 18516 KB Output is correct
6 Correct 16 ms 18516 KB Output is correct
7 Correct 15 ms 18516 KB Output is correct
8 Correct 16 ms 18516 KB Output is correct
9 Correct 16 ms 18516 KB Output is correct
10 Correct 23 ms 19324 KB Output is correct
11 Correct 21 ms 19284 KB Output is correct
12 Correct 27 ms 19292 KB Output is correct
13 Correct 21 ms 19284 KB Output is correct
14 Correct 24 ms 19312 KB Output is correct
15 Correct 22 ms 19284 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17928 KB Output is correct
2 Correct 63 ms 22088 KB Output is correct
3 Correct 500 ms 42932 KB Output is correct
4 Correct 368 ms 41400 KB Output is correct
5 Correct 427 ms 44220 KB Output is correct
6 Correct 438 ms 42736 KB Output is correct
7 Correct 485 ms 41712 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17928 KB Output is correct
2 Correct 63 ms 22088 KB Output is correct
3 Correct 500 ms 42932 KB Output is correct
4 Correct 368 ms 41400 KB Output is correct
5 Correct 427 ms 44220 KB Output is correct
6 Correct 438 ms 42736 KB Output is correct
7 Correct 485 ms 41712 KB Output is correct
8 Correct 386 ms 42800 KB Output is correct
9 Correct 312 ms 42252 KB Output is correct
10 Correct 349 ms 42640 KB Output is correct
11 Correct 347 ms 42732 KB Output is correct
12 Correct 328 ms 42116 KB Output is correct
13 Correct 321 ms 42960 KB Output is correct
14 Correct 449 ms 44060 KB Output is correct
15 Correct 312 ms 43476 KB Output is correct
16 Correct 488 ms 41576 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 16 ms 18456 KB Output is correct
3 Correct 14 ms 18456 KB Output is correct
4 Correct 15 ms 18484 KB Output is correct
5 Correct 16 ms 18516 KB Output is correct
6 Correct 16 ms 18516 KB Output is correct
7 Correct 15 ms 18516 KB Output is correct
8 Correct 16 ms 18516 KB Output is correct
9 Correct 16 ms 18516 KB Output is correct
10 Correct 23 ms 19324 KB Output is correct
11 Correct 21 ms 19284 KB Output is correct
12 Correct 27 ms 19292 KB Output is correct
13 Correct 21 ms 19284 KB Output is correct
14 Correct 24 ms 19312 KB Output is correct
15 Correct 22 ms 19284 KB Output is correct
16 Correct 9 ms 17928 KB Output is correct
17 Correct 63 ms 22088 KB Output is correct
18 Correct 500 ms 42932 KB Output is correct
19 Correct 368 ms 41400 KB Output is correct
20 Correct 427 ms 44220 KB Output is correct
21 Correct 438 ms 42736 KB Output is correct
22 Correct 485 ms 41712 KB Output is correct
23 Correct 386 ms 42800 KB Output is correct
24 Correct 312 ms 42252 KB Output is correct
25 Correct 349 ms 42640 KB Output is correct
26 Correct 347 ms 42732 KB Output is correct
27 Correct 328 ms 42116 KB Output is correct
28 Correct 321 ms 42960 KB Output is correct
29 Correct 449 ms 44060 KB Output is correct
30 Correct 312 ms 43476 KB Output is correct
31 Correct 488 ms 41576 KB Output is correct
32 Correct 4482 ms 208440 KB Output is correct
33 Correct 3667 ms 207816 KB Output is correct
34 Correct 4019 ms 210532 KB Output is correct
35 Correct 4312 ms 210576 KB Output is correct
36 Correct 3836 ms 208000 KB Output is correct
37 Correct 3851 ms 210624 KB Output is correct
38 Correct 4641 ms 222916 KB Output is correct
39 Correct 3902 ms 222980 KB Output is correct
40 Correct 2738 ms 205548 KB Output is correct
41 Correct 4948 ms 203692 KB Output is correct
42 Correct 5308 ms 206056 KB Output is correct
43 Correct 5198 ms 206084 KB Output is correct
44 Correct 4765 ms 211292 KB Output is correct