Submission #316279

#	Time	Username	Problem	Language	Result	Execution time	Memory
316279		shrek12357	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	403 ms	6000 KiB

joi2019_ho_t4

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0); 

int main() {
	int n;
	cin >> n;
	vector<int> v1, v2;
	ll ans = 0;
	for (int i = 0; i < 2*n; i++) {
		ll a, b;
		cin >> a >> b;
		if (b >= 2) {
			ans += b - 2;
			b = 2;
		}
		else {
			ans += 1 - b;
			b = 1;
		}
		if (a >= n) {
			ans += a - n;
			a = n;
		}
		else if (a <= 1) {
			ans += 1 - a;
			a = 1;
		}
		if (b == 1) {
			v1.push_back(a);
		}
		else {
			v2.push_back(a);
		}
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	queue<ll> q1, q2;
	int idx1 = 0, idx2 = 0;
	for (int i = 1; i <= n; i++) {
		q1.push(i);
		q2.push(i);
		while (q1.size() > 0 && idx1 < v1.size() && v1[idx1] <= i) {
			ans += abs(q1.front() - v1[idx1]);
			idx1++;
			q1.pop();
		}
		while (q2.size() > 0 && idx2 < v2.size() && v2[idx2] <= i) {
			ans += abs(q2.front() - v2[idx2]);
			idx2++;
			q2.pop();
		}
		while (q2.size() > 0 && idx1 < v1.size() && v1[idx1] <= i) {
			ans += abs(q2.front() - v1[idx1]) + 1;
			idx1++;
			q2.pop();	
		}
		while (q1.size() > 0 && idx2 < v2.size() && v2[idx2] <= i) {
			ans += abs(q1.front() - v2[idx2]) + 1;
			idx2++;
			q1.pop();
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:55:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (q1.size() > 0 && idx1 < v1.size() && v1[idx1] <= i) {
      |                           ~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:60:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   while (q2.size() > 0 && idx2 < v2.size() && v2[idx2] <= i) {
      |                           ~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while (q2.size() > 0 && idx1 < v1.size() && v1[idx1] <= i) {
      |                           ~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:70:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   while (q1.size() > 0 && idx2 < v2.size() && v2[idx2] <= i) {
      |                           ~~~~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63