oj.uz

Submission #626717

# Submission time Handle Problem Language Result Execution time Memory
626717 2022-08-11T17:02:16 Z CSQ31 Road Construction (JOI21_road_construction) C++17
38 / 100
 4304 ms 2086628 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);
	for(int i=0;i<n;i++){
		int cur = root;
		if(r[p[i].se] != n-1){
			for(int j=0;j<k;j++){
				pii res = query(cur,r[p[i].se]+1,n-1,0,n-1);
				//cout<<cur<<" "<<res.fi<<" "<<res.se<<'\n';
				if(res.fi == -INF)break;
				ll c = p[i].fi - p[i].se;
				c-=res.fi;
				//cout<<c<<'\n';
				glo.pb(c);
				cur = upd(cur,0,n-1,res.se,-INF);
			}
		}
		root = upd(root,0,n-1,id[i],p[i].fi-p[i].se);
	}
	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 235 ms 50804 KB Output is correct
2 Correct 225 ms 50776 KB Output is correct
3 Correct 115 ms 25604 KB Output is correct
4 Correct 102 ms 24988 KB Output is correct
5 Correct 201 ms 57180 KB Output is correct
6 Correct 82 ms 44740 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 174472 KB Output is correct
2 Correct 513 ms 174520 KB Output is correct
3 Correct 99 ms 46396 KB Output is correct
4 Correct 379 ms 174160 KB Output is correct
5 Correct 363 ms 174424 KB Output is correct
6 Correct 368 ms 174424 KB Output is correct
7 Correct 390 ms 173752 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 243116 KB Output is correct
2 Correct 1379 ms 243288 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 242 ms 97344 KB Output is correct
5 Correct 622 ms 219852 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 243116 KB Output is correct
2 Correct 1379 ms 243288 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 242 ms 97344 KB Output is correct
5 Correct 622 ms 219852 KB Output is correct
6 Correct 3512 ms 926396 KB Output is correct
7 Correct 3253 ms 926344 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 3264 ms 927428 KB Output is correct
11 Correct 223 ms 99748 KB Output is correct
12 Correct 1881 ms 902808 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 50804 KB Output is correct
2 Correct 225 ms 50776 KB Output is correct
3 Correct 115 ms 25604 KB Output is correct
4 Correct 102 ms 24988 KB Output is correct
5 Correct 201 ms 57180 KB Output is correct
6 Correct 82 ms 44740 KB Output is correct
7 Runtime error 4304 ms 2086628 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 50804 KB Output is correct
2 Correct 225 ms 50776 KB Output is correct
3 Correct 115 ms 25604 KB Output is correct
4 Correct 102 ms 24988 KB Output is correct
5 Correct 201 ms 57180 KB Output is correct
6 Correct 82 ms 44740 KB Output is correct
7 Correct 516 ms 174472 KB Output is correct
8 Correct 513 ms 174520 KB Output is correct
9 Correct 99 ms 46396 KB Output is correct
10 Correct 379 ms 174160 KB Output is correct
11 Correct 363 ms 174424 KB Output is correct
12 Correct 368 ms 174424 KB Output is correct
13 Correct 390 ms 173752 KB Output is correct
14 Correct 1521 ms 243116 KB Output is correct
15 Correct 1379 ms 243288 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 242 ms 97344 KB Output is correct
18 Correct 622 ms 219852 KB Output is correct
19 Correct 3512 ms 926396 KB Output is correct
20 Correct 3253 ms 926344 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 3264 ms 927428 KB Output is correct
24 Correct 223 ms 99748 KB Output is correct
25 Correct 1881 ms 902808 KB Output is correct
26 Runtime error 4304 ms 2086628 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -