oj.uz

Submission #623059

# Submission time Handle Problem Language Result Execution time Memory
623059 2022-08-05T06:45:27 Z CSQ31 Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
//consider the case where we only need k smallest from two different set of points
//if can do this in some reasonable time then apply zs bit trick
//+log factor
//need <= log^3 maybe?
//ok two set need log^2(?)
#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];
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){
		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),cxy(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();
		vector<multiset<int>::iterator>it(s);
		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];
			glo.push_back(c - v.fi);
			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();
		vector<multiset<int>::iterator>it(s);
		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];
			glo.push_back(c - v.fi);
			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 115 ms 100964 KB Output is correct
2 Correct 117 ms 100928 KB Output is correct
3 Correct 88 ms 98984 KB Output is correct
4 Correct 92 ms 99016 KB Output is correct
5 Correct 110 ms 99896 KB Output is correct
6 Correct 72 ms 98484 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3582 ms 215040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3582 ms 215040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 100964 KB Output is correct
2 Correct 117 ms 100928 KB Output is correct
3 Correct 88 ms 98984 KB Output is correct
4 Correct 92 ms 99016 KB Output is correct
5 Correct 110 ms 99896 KB Output is correct
6 Correct 72 ms 98484 KB Output is correct
7 Execution timed out 10091 ms 1589944 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 100964 KB Output is correct
2 Correct 117 ms 100928 KB Output is correct
3 Correct 88 ms 98984 KB Output is correct
4 Correct 92 ms 99016 KB Output is correct
5 Correct 110 ms 99896 KB Output is correct
6 Correct 72 ms 98484 KB Output is correct
7 Runtime error 4196 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -