oj.uz

Submission #623095

# Submission time Handle Problem Language Result Execution time Memory
623095 2022-08-05T07:32:21 Z CSQ31 Road Construction (JOI21_road_construction) C++17
32 / 100
 8306 ms 2097152 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);
const int MAXN = 2000000;
vector<ll>glo;
multiset<int>fen[MAXN];
multiset<int>::iterator it[MAXN];
vector<int>touch;
void upd(int i,int n,int v){
	for(;i<=n;i+=i&(-i))fen[i].insert(v);
}
void query(int i){
	while(i>0){
		touch.pb(i);
		i-=i&(-i);
	}
}
#define fi first
#define se second 
typedef pair<int,int> pii;
int main()
{
	owo
	int n,k;
	cin>>n>>k;
	vector<array<int,2>>p(n);
	vector<int>cy(n);
	for(int i=0;i<n;i++)cin>>p[i][0]>>p[i][1];
	sort(all(p));
	vector<int>crd;
	for(int i=0;i<n;i++)crd.push_back(p[i][1]);
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++)cy[i] = lower_bound(all(crd),p[i][1]) - crd.begin()+1;
	int m = crd.size();
	//y(i) >= y(j) case
	//we use x(i)+y(i) - x(j) - y(j)
	for(int i=0;i<n;i++){
		touch.clear();
		query(cy[i]);
		priority_queue<pii,vector<pii>,greater<pii>>pq;
		int s = touch.size();
		for(int i=0;i<s;i++){
			if(fen[touch[i]].empty())continue;
			it[i] = fen[touch[i]].begin();
			pq.push({*it[i],i});
		}
		for(int cnt=0;cnt<k;cnt++){
			if(pq.empty())break;
			pii v = pq.top();
			pq.pop();
			ll c = p[i][0] + p[i][1];
			c+=v.fi;
			glo.push_back(c);
			it[v.se]++;
			if(it[v.se] == fen[touch[v.se]].end())continue;
			pq.push({*it[v.se],v.se});
			
		}
	    upd(cy[i],m,-(p[i][0]+p[i][1]));
	}
	//y(i) < y(j) case
	//we use x(i) - y(i) - (x(j)-y(j)) 
	for(int i=1;i<=m;i++)fen[i].clear(); //i need to do the opposite directly
	for(int i=0;i<n;i++){
		touch.clear();
		cy[i] = m-cy[i]+1;
		query(cy[i]-1);
		priority_queue<pii,vector<pii>,greater<pii>>pq;
		int s = touch.size();
		for(int i=0;i<s;i++){
			if(fen[touch[i]].empty())continue;
			it[i] = fen[touch[i]].begin();
			pq.push({*it[i],i});
		}
		for(int cnt=0;cnt<k;cnt++){
			if(pq.empty())break;
			pii v = pq.top();
			pq.pop();
			ll c = p[i][0] - p[i][1];
			c+=v.fi;
			glo.push_back(c);
			it[v.se]++;
			if(it[v.se] == fen[touch[v.se]].end())continue;
			pq.push({*it[v.se],v.se});
			
		}
	    upd(cy[i],m,-(p[i][0]-p[i][1]));
	}
	sort(all(glo));
	//for(int x:glo)cout<<x<<" ";
	//cout<<'\n';
	for(int i=0;i<k;i++)cout<<glo[i]<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 116580 KB Output is correct
2 Correct 128 ms 116640 KB Output is correct
3 Correct 95 ms 114624 KB Output is correct
4 Correct 92 ms 114656 KB Output is correct
5 Correct 118 ms 115536 KB Output is correct
6 Correct 81 ms 114108 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 4620 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3545 ms 225708 KB Output is correct
2 Correct 3488 ms 224736 KB Output is correct
3 Correct 51 ms 109772 KB Output is correct
4 Correct 228 ms 130356 KB Output is correct
5 Correct 903 ms 175892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3545 ms 225708 KB Output is correct
2 Correct 3488 ms 224736 KB Output is correct
3 Correct 51 ms 109772 KB Output is correct
4 Correct 228 ms 130356 KB Output is correct
5 Correct 903 ms 175892 KB Output is correct
6 Correct 4585 ms 290672 KB Output is correct
7 Correct 4390 ms 291332 KB Output is correct
8 Correct 52 ms 109772 KB Output is correct
9 Correct 51 ms 109772 KB Output is correct
10 Correct 4351 ms 291764 KB Output is correct
11 Correct 350 ms 159352 KB Output is correct
12 Correct 1309 ms 238260 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 116580 KB Output is correct
2 Correct 128 ms 116640 KB Output is correct
3 Correct 95 ms 114624 KB Output is correct
4 Correct 92 ms 114656 KB Output is correct
5 Correct 118 ms 115536 KB Output is correct
6 Correct 81 ms 114108 KB Output is correct
7 Runtime error 8306 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 116580 KB Output is correct
2 Correct 128 ms 116640 KB Output is correct
3 Correct 95 ms 114624 KB Output is correct
4 Correct 92 ms 114656 KB Output is correct
5 Correct 118 ms 115536 KB Output is correct
6 Correct 81 ms 114108 KB Output is correct
7 Runtime error 4620 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -