oj.uz

Submission #626727

# Submission time Handle Problem Language Result Execution time Memory
626727 2022-08-11T17:18:09 Z CSQ31 Road Construction (JOI21_road_construction) C++17
100 / 100
 2309 ms 245560 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define fi first
#define se second 
#define sz(a) (int)(a.size())
typedef pair<int,int> pii;
vector<ll>glo;
const int MAXN = 1e8,INF = 2e9+1;
pii t[MAXN];
int ch[2][MAXN];
int ndcnt = 0;
int nwnode(int v = -1){
	ndcnt++;
	int u = ndcnt;
	t[u] = {-INF,0};
	if(v!=-1){
		t[u] = t[v];
		ch[0][u] = ch[0][v];
		ch[1][u] = ch[1][v];
	}
	return u;
}
void pull(int v){
	t[v] = {-INF,0};
	if(ch[0][v])t[v] = max(t[v],t[ch[0][v]]);
	if(ch[1][v])t[v] = max(t[v],t[ch[1][v]]);
}
int build(int l,int r){
	if(l==r){
		int u = nwnode();
		t[u].se = l;
		return u;
	}
	int u = nwnode();
	int tm = (l+r)/2;
	ch[0][u] = build(l,tm);
	ch[1][u] = build(tm+1,r);
	pull(u);
	return u;
}
int upd(int v,int l,int r,int pos,int val){
	if(l==r){
		int u = nwnode();
		t[u] = {val,pos};
		//cout<<l<<" "<<r<<" "<<t[u].fi<<" "<<t[u].se<<'\n';
		return u;
	}
	int u = nwnode(v);
	int tm = (l+r)/2;
	if(pos <= tm)ch[0][u] = upd(ch[0][v],l,tm,pos,val);
	else ch[1][u] = upd(ch[1][v],tm+1,r,pos,val);
	pull(u);
	//cout<<l<<" "<<r<<" "<<t[u].fi<<" "<<t[u].se<<'\n';
	return u;
}
pii query(int v,int l,int r,int tl,int tr){
	if(l>r)return {-INF,0};
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	return max(query(ch[0][v],l,min(r,tm),tl,tm),
	           query(ch[1][v],max(l,tm+1),r,tm+1,tr));
}
void reset(){
	for(int i=0;i<=ndcnt;i++){
		t[i] = {-INF,0};
		ch[0][i] = ch[1][i] = 0;
	}
	ndcnt = 0;
}
vector<array<int,4>>seg;
void fetch(int v,int l,int r,int tl,int tr){
	//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<'\n';
	if(l>r)return;
	if(l==tl && r==tr){
		seg.pb({v,l,r,0});
		return;
	}
	int tm = (tl+tr)/2;
	fetch(ch[0][v],l,min(r,tm),tl,tm);
	fetch(ch[1][v],max(l,tm+1),r,tm+1,tr);
}
int main()
{
	owo
	int n,k;
	cin>>n>>k;
	vector<pii>p(n),y(n);
	vector<int>id(n);
	for(int i=0;i<n;i++)cin>>p[i].fi>>p[i].se;
	sort(all(p));
	for(int i=0;i<n;i++){
		y[i].fi = p[i].se;
		y[i].se = i;
	}
	sort(all(y));
	map<int,int>r; //right border of fixed value of y
	//cout<<"sort\n";
	for(int i=0;i<n;i++){
		//cout<<p[i].fi<<" "<<p[i].se<<'\n';
		r[y[i].fi] = i;
		id[y[i].se] = i;
	}
	//for(int i=0;i<n;i++)cout<<id[i]<<" ";
	//cout<<'\n';
	int root = build(0,n-1);
	for(int i=0;i<n;i++){
		int oldsz = sz(seg);
		fetch(root,0,r[p[i].se],0,n-1);
		for(int j=oldsz;j<sz(seg);j++)seg[j][3] = i;
		root = upd(root,0,n-1,id[i],p[i].fi+p[i].se);
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
	int m = sz(seg);
	for(int i=0;i<m;i++){
		pii res = t[seg[i][0]];
		if(res.fi == -INF)continue;
		int id = seg[i][3];
		ll c = p[id].fi+p[id].se;
		c-=res.fi;
		pq.push({c,i});
	}
	for(int j=0;j<k;j++){
		if(pq.empty())break;
		glo.pb(pq.top().fi);
		int i = pq.top().se;
		pq.pop();
		
		pii res = t[seg[i][0]];
		seg[i][0] = upd(seg[i][0],seg[i][1],seg[i][2],res.se,-INF);
		
		res = t[seg[i][0]];
		if(res.fi == -INF)continue;
		int id = seg[i][3];
		ll c = p[id].fi+p[id].se;
		c-=res.fi;
		pq.push({c,i});
		
	}
	reset();
	root = build(0,n-1);
	seg.clear();
	while(!pq.empty())pq.pop();
    for(int i=0;i<n;i++){
		if(r[p[i].se] != n-1){
			int oldsz = sz(seg);
			fetch(root,r[p[i].se]+1,n-1,0,n-1);
			for(int j=oldsz;j<sz(seg);j++)seg[j][3] = i;
		}
		root = upd(root,0,n-1,id[i],p[i].fi-p[i].se);
	}
	m = sz(seg);
	//cout<<m<<'\n';
	for(int i=0;i<m;i++){
		pii res = t[seg[i][0]];
		if(res.fi == -INF)continue;
		int id = seg[i][3];
		ll c = p[id].fi-p[id].se;
		c-=res.fi;
		pq.push({c,i});
	}
	for(int j=0;j<k;j++){
		if(pq.empty())break;
		glo.pb(pq.top().fi);
		int i = pq.top().se;
		pq.pop();
		
		pii res = t[seg[i][0]];
		seg[i][0] = upd(seg[i][0],seg[i][1],seg[i][2],res.se,-INF);
		
		res = t[seg[i][0]];
		if(res.fi == -INF)continue;
		int id = seg[i][3];
		ll c = p[id].fi-p[id].se;
		c-=res.fi;
		pq.push({c,i});
		
	}
	sort(all(glo));
	//for(ll x:glo)cout<<x<<'\n';
	for(int i=0;i<k;i++)cout<<glo[i]<<'\n';
	//cout<<'\n';
	
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 42440 KB Output is correct
2 Correct 263 ms 42576 KB Output is correct
3 Correct 126 ms 22584 KB Output is correct
4 Correct 106 ms 24956 KB Output is correct
5 Correct 184 ms 41156 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 174412 KB Output is correct
2 Correct 685 ms 174400 KB Output is correct
3 Correct 101 ms 46392 KB Output is correct
4 Correct 433 ms 174192 KB Output is correct
5 Correct 397 ms 174520 KB Output is correct
6 Correct 404 ms 174484 KB Output is correct
7 Correct 459 ms 173760 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1819 ms 200220 KB Output is correct
2 Correct 1736 ms 200300 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 255 ms 97256 KB Output is correct
5 Correct 812 ms 188180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1819 ms 200220 KB Output is correct
2 Correct 1736 ms 200300 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 255 ms 97256 KB Output is correct
5 Correct 812 ms 188180 KB Output is correct
6 Correct 1735 ms 200252 KB Output is correct
7 Correct 1772 ms 200356 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1750 ms 199260 KB Output is correct
11 Correct 252 ms 97512 KB Output is correct
12 Correct 804 ms 188348 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 42440 KB Output is correct
2 Correct 263 ms 42576 KB Output is correct
3 Correct 126 ms 22584 KB Output is correct
4 Correct 106 ms 24956 KB Output is correct
5 Correct 184 ms 41156 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 1022 ms 110004 KB Output is correct
8 Correct 1012 ms 112004 KB Output is correct
9 Correct 116 ms 24936 KB Output is correct
10 Correct 929 ms 108692 KB Output is correct
11 Correct 886 ms 110400 KB Output is correct
12 Correct 559 ms 118460 KB Output is correct
13 Correct 562 ms 118876 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 42440 KB Output is correct
2 Correct 263 ms 42576 KB Output is correct
3 Correct 126 ms 22584 KB Output is correct
4 Correct 106 ms 24956 KB Output is correct
5 Correct 184 ms 41156 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 554 ms 174412 KB Output is correct
8 Correct 685 ms 174400 KB Output is correct
9 Correct 101 ms 46392 KB Output is correct
10 Correct 433 ms 174192 KB Output is correct
11 Correct 397 ms 174520 KB Output is correct
12 Correct 404 ms 174484 KB Output is correct
13 Correct 459 ms 173760 KB Output is correct
14 Correct 1819 ms 200220 KB Output is correct
15 Correct 1736 ms 200300 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 255 ms 97256 KB Output is correct
18 Correct 812 ms 188180 KB Output is correct
19 Correct 1735 ms 200252 KB Output is correct
20 Correct 1772 ms 200356 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1750 ms 199260 KB Output is correct
24 Correct 252 ms 97512 KB Output is correct
25 Correct 804 ms 188348 KB Output is correct
26 Correct 1022 ms 110004 KB Output is correct
27 Correct 1012 ms 112004 KB Output is correct
28 Correct 116 ms 24936 KB Output is correct
29 Correct 929 ms 108692 KB Output is correct
30 Correct 886 ms 110400 KB Output is correct
31 Correct 559 ms 118460 KB Output is correct
32 Correct 562 ms 118876 KB Output is correct
33 Correct 2309 ms 245548 KB Output is correct
34 Correct 2265 ms 245560 KB Output is correct
35 Correct 2036 ms 240388 KB Output is correct
36 Correct 1103 ms 241276 KB Output is correct
37 Correct 1083 ms 240976 KB Output is correct
38 Correct 1255 ms 239160 KB Output is correct