oj.uz

Submission #348263

# Submission time Handle Problem Language Result Execution time Memory
348263 2021-01-14T12:38:08 Z mario05092929 Palembang Bridges (APIO15_bridge) C++11
22 / 100
 139 ms 7640 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 5e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,k,m;
ll pre,lsum,rsum,cnt,kl[100005],kr[100005];
priority_queue <ll> l,r;
pl a[100005];

bool cmp(pl x,pl y) {
	return x.x+x.y < y.x+y.y;
}

void update(ll x,ll y) {
	l.push(x), l.push(y);
	lsum += x+y;
	r.push(-l.top());
	rsum += l.top();
	lsum -= l.top();
	l.pop();
	r.push(-l.top());
	rsum += l.top();
	lsum -= l.top();
	l.pop();
	l.push(-r.top());
	lsum += -r.top();
	rsum -= -r.top();
	r.pop();
	cnt++;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> k >> n;
	for(int i = 1;i <= n;i++) {
		char op1,op2; int x1,x2;
		cin >> op1 >> x1 >> op2 >> x2;
		if(op1^op2) a[++m] = {x1,x2};
		else pre += abs(x1-x2);
	}
	sort(a+1,a+m+1,cmp);
	for(int i = 1;i <= m;i++) {
		update(a[i].x,a[i].y);
		kl[i] = rsum-lsum+cnt;
	}
	while(!l.empty()) l.pop();
	while(!r.empty()) r.pop();
	lsum = rsum = cnt = 0;
	for(int i = m;i >= 1;i--) {
		update(a[i].x,a[i].y);
		kr[i] = rsum-lsum+cnt;
	}
	if(k == 1) {
		cout << kl[m]+pre;
		return 0;
	}
	ll ans = llINF;
	for(int i = 1;i <= m;i++) {
		ans = min(ans,kl[i]+kr[i+1]);
	}
	cout << ans+pre;
}

Compilation message

bridge.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
bridge.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
bridge.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 67 ms 5976 KB Output is correct
13 Correct 139 ms 7640 KB Output is correct
14 Correct 115 ms 5976 KB Output is correct
15 Correct 78 ms 4724 KB Output is correct
16 Correct 83 ms 7000 KB Output is correct
17 Correct 118 ms 7640 KB Output is correct
18 Correct 115 ms 7256 KB Output is correct
19 Correct 119 ms 7640 KB Output is correct
20 Correct 79 ms 7256 KB Output is correct
21 Correct 117 ms 7384 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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