oj.uz

Submission #73216

# Submission time Handle Problem Language Result Execution time Memory
73216 2018-08-28T04:58:41 Z 박상수(#2273) Radio (Balkan15_RADIO) C++11
100 / 100
 418 ms 19584 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int N, K;
ll X[100010], P[100010], S[100010];
ll ans;
int ac[100010];

struct event{
	event(){}
	event(ll x, int a, int fa, int b, int fb) : x(x), a(a), fa(fa), b(b), fb(fb) {}
	event(ll x, int a, int fa) : x(x), a(a), fa(fa), b(a), fb(-123456789) {}
	ll x;
	int a, fa, b, fb;
	bool operator>(const event &rhs)const{
		return x > rhs.x;
	}
};

priority_queue <event, vector<event>, greater<event> > Q;

priority_queue <pll> pq1[3];
priority_queue <pll, vector<pll>, greater<pll> > pq2[3];
int in_k[100010];

void Ins(int a, int b) {
	while(!pq1[a].empty()) {
		pll t = pq1[a].top();
		if(ac[t.Se] == a-1 && in_k[t.Se] == 1) break;
		pq1[a].pop();
	}
	while(!pq2[b].empty()) {
		pll t = pq2[b].top();
		if(ac[t.Se] == b-1 && in_k[t.Se] == 0) break;
		pq2[b].pop();
	}
	if(pq1[a].empty() || pq2[b].empty()) return;
	pll ta = pq1[a].top(), tb = pq2[b].top();
	int ar = a - 1, br = b - 1;
	ll vx = (tb.Fi - ta.Fi) / (ar - br);
	Q.push(event(vx, (int)ta.Se, ac[ta.Se], (int)tb.Se, ac[tb.Se]));
}

ll get_i(int a) {
	if(ac[a] == -1) return X[a] - P[a] + S[a];
	else if(ac[a] == 0) return S[a];
	else return -X[a] - P[a] + S[a];
}

void Ins() {
	Ins(1, 0); Ins(2, 0); Ins(2, 1);
}

void solve(){
	scanf("%d%d", &N, &K);
	for(int i=1;i<=N;i++) scanf("%lld%lld%lld", X+i, P+i, S+i);
	for(int i=1;i<=N;i++) X[i] *= 2, P[i] *= 2, S[i] *= 2, ans -= S[i];
	
	ll now_a = -K, now_b = 0;
	for(int i=1;i<=N;i++) {
		pq1[0].push(pll(X[i] - P[i] + S[i], i)), in_k[i] = 1;
		ac[i] = -1;
		now_b += get_i(i);
		Q.push(event(X[i] - P[i], i, -1));
		Q.push(event(X[i] + P[i], i, 0));
	}
	
	while(sz(pq1[0]) > K) {
		int u = (int)pq1[0].top().Se;
		in_k[u] = 0, now_b -= get_i(u);
		pq2[0].push(pq1[0].top()), pq1[0].pop();
	}
	
	ll res = 1e18;
	while(!Q.empty()) {
		event t = Q.top(); Q.pop();
		if(t.a == t.b) {
			res = min(res, now_a * t.x + now_b);
			if(in_k[t.a]) now_b -= get_i(t.a);
			ac[t.a]++;
			if(in_k[t.a]) now_a++, now_b += get_i(t.a);
			if(in_k[t.a]) {
				pq1[ac[t.a]+1].push(pll(get_i(t.a), t.a));
				Ins();
			}
			else {
				pq2[ac[t.a]+1].push(pll(get_i(t.a), t.a));
				Ins();
			}
		}
		else {
			if(ac[t.a] != t.fa || ac[t.b] != t.fb) continue;
			if(in_k[t.a] == 0 || in_k[t.b] == 1) continue;
			in_k[t.a] = 0; in_k[t.b] = 1;
			now_a -= ac[t.a];
			now_a += ac[t.b];
			now_b -= get_i(t.a);
			now_b += get_i(t.b);
			pq2[ac[t.a]+1].push(pll(get_i(t.a), t.a));
			pq1[ac[t.b]+1].push(pll(get_i(t.b), t.b));
			Ins();
		}
	}
	
	printf("%lld\n", (ans + res) >> 1);
	
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d\n", tc);
		solve();
	}
	return 0;
};

Compilation message

code1.cpp: In function 'void solve()':
code1.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
code1.cpp:85:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%lld%lld%lld", X+i, P+i, S+i);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 2 ms 520 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 520 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 4 ms 696 KB Output is correct
5 Correct 3 ms 700 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 4 ms 720 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 6 ms 748 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1448 KB Output is correct
2 Correct 29 ms 3484 KB Output is correct
3 Correct 64 ms 7848 KB Output is correct
4 Correct 145 ms 12632 KB Output is correct
5 Correct 114 ms 14208 KB Output is correct
6 Correct 173 ms 15108 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15108 KB Output is correct
2 Correct 78 ms 15108 KB Output is correct
3 Correct 130 ms 15108 KB Output is correct
4 Correct 182 ms 15108 KB Output is correct
5 Correct 199 ms 15108 KB Output is correct
6 Correct 311 ms 15632 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15632 KB Output is correct
2 Correct 78 ms 15632 KB Output is correct
3 Correct 102 ms 15632 KB Output is correct
4 Correct 162 ms 15632 KB Output is correct
5 Correct 238 ms 15632 KB Output is correct
6 Correct 418 ms 15804 KB Output is correct
7 Correct 279 ms 16384 KB Output is correct
8 Correct 336 ms 16384 KB Output is correct
9 Correct 282 ms 16384 KB Output is correct
10 Correct 217 ms 19584 KB Output is correct