Submission #1404044


Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 1e6 + 6, mod = (int) 0;
int to_add[N], mark[N], res[N], a[N], b[N], c[N], p[N], add[N];
set<int> q[N];
int main() {
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int j = 0; j < n; ++j)
		cin >> a[j] >> b[j];	
	for (int j = 0; j < n + 1; ++j)
		cin >> c[j];
	sort(c, c + n + 1);
	for (int j = 0; j < n; ++j) {
		a[j] = lower_bound(c, c + n + 1, a[j]) - c;
		b[j] = lower_bound(c, c + n + 1, b[j]) - c;
	}
	for (int j = 0; j < n + 1; ++j) p[j]--;
	for (int j = 0; j < n; ++j) p[a[j]]++;
	for (int j = 1; j < n + 1; ++j) p[j] += p[j - 1];
	for (int j = 0; j < n; ++j) {
		if (a[j] > b[j]) {
			q[a[j] - 1].insert(j);
		}
	}
	int init_res = 0;
	set<pair<int, int>> st;
	
	for (int pos = n; pos >= 0; --pos) {
		for (int j : q[pos]) st.insert(mp(b[j], j));
		add[pos] += add[pos + 1];
		p[pos] += add[pos];
		while (p[pos] < -1) {
			if (st.size()) {
				auto cur = *(st.begin());
				int l = cur.first;
				st.erase(cur);
				if (l > pos) continue;
				mark[cur.second] = 1;
				init_res++;
				to_add[a[cur.second] - 1]++;
				to_add[pos]--;
				add[pos]++;
				p[pos]++;
				if (l >= 1) {
					add[l - 1]--;
				}
			} else {
				init_res = -1e9;
				break;	
			}
		}		
	}
	for (int pos = n; pos >= 0; --pos) {
		to_add[pos] += to_add[pos + 1];
		p[pos] += to_add[pos];
	}
	if (init_res >= 0) {
		res[0] = n - init_res;
		for (int j = 0; j < n + 1; ++j) q[j].clear();
		for (int j = 0; j < n; ++j) if (!mark[j]) {
			if (b[j] < a[j]) {
				q[b[j]].insert(j);
			}	
		}
		st.clear();
		memset(add, 0, sizeof add);
		for (int pos = 0; pos <= n; ++pos) {
			res[pos + 1] = res[pos];
			for (int j : q[pos]) st.insert(mp(-a[j], j));
			if (pos >= 1) add[pos] += add[pos - 1];
			p[pos] += add[pos];
			while (p[pos] == -1) {
				if (st.size()) {
					auto cur = *(st.begin());
					int r = -cur.first;
					st.erase(cur);
					if (r <= pos) continue;
					mark[cur.second] = 1;
					res[pos + 1]--;
					add[pos]++;
					p[pos]++;
					add[r]--;
				} else {
					res[pos + 1] = -1e9;
					break;	
				}
			}		
		}
		for (int j = 0; j <= n + 1; ++j) {
			res[j] = max(res[j], -1);	
		}
	} else {
		memset(res, -1, sizeof res);
	}
	int qn;
	cin >> qn;
	while (qn--) {
		int x, y;
		cin >> x >> y;
		x = lower_bound(c, c + n + 1, x) - c;
		y = lower_bound(c, c + n + 1, y) - c;
		int ansx = (res[x] == -1 ? -1 : res[x] + 1);
		int ansy = (res[y] == -1 ? -1 : res[y]);
		cout << max(ansx, ansy) << '\n';
	}
}



Submission Info

Submission Time
Task F - Two Faced Cards
User Reyna
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 3593 Byte
Status AC
Exec Time 361 ms
Memory 73728 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 2000 / 2000
Status
AC × 3
AC × 61
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt
Case Name Status Exec Time Memory
sample_01.txt AC 22 ms 63744 KB
sample_02.txt AC 22 ms 63744 KB
sample_03.txt AC 22 ms 63744 KB
subtask_1_01.txt AC 111 ms 66688 KB
subtask_1_02.txt AC 178 ms 68992 KB
subtask_1_03.txt AC 76 ms 65280 KB
subtask_1_04.txt AC 114 ms 70144 KB
subtask_1_05.txt AC 158 ms 66048 KB
subtask_1_06.txt AC 258 ms 70016 KB
subtask_1_07.txt AC 165 ms 71552 KB
subtask_1_08.txt AC 165 ms 70528 KB
subtask_1_09.txt AC 212 ms 71040 KB
subtask_1_10.txt AC 112 ms 68608 KB
subtask_1_11.txt AC 98 ms 66176 KB
subtask_1_12.txt AC 110 ms 67072 KB
subtask_1_13.txt AC 199 ms 68352 KB
subtask_1_14.txt AC 88 ms 67328 KB
subtask_1_15.txt AC 100 ms 69504 KB
subtask_1_16.txt AC 108 ms 65152 KB
subtask_1_17.txt AC 333 ms 73472 KB
subtask_1_18.txt AC 59 ms 67072 KB
subtask_1_19.txt AC 269 ms 69120 KB
subtask_1_20.txt AC 219 ms 70400 KB
subtask_1_21.txt AC 336 ms 68992 KB
subtask_1_22.txt AC 333 ms 73728 KB
subtask_1_23.txt AC 338 ms 68992 KB
subtask_1_24.txt AC 335 ms 73728 KB
subtask_1_25.txt AC 360 ms 73728 KB
subtask_1_26.txt AC 333 ms 73216 KB
subtask_1_27.txt AC 311 ms 71808 KB
subtask_1_28.txt AC 329 ms 71296 KB
subtask_1_29.txt AC 357 ms 73728 KB
subtask_1_30.txt AC 339 ms 73088 KB
subtask_1_31.txt AC 310 ms 71808 KB
subtask_1_32.txt AC 333 ms 71296 KB
subtask_1_33.txt AC 356 ms 73728 KB
subtask_1_34.txt AC 334 ms 73088 KB
subtask_1_35.txt AC 312 ms 71296 KB
subtask_1_36.txt AC 322 ms 71296 KB
subtask_1_37.txt AC 350 ms 73728 KB
subtask_1_38.txt AC 329 ms 73088 KB
subtask_1_39.txt AC 315 ms 72704 KB
subtask_1_40.txt AC 333 ms 71296 KB
subtask_1_41.txt AC 322 ms 68992 KB
subtask_1_42.txt AC 273 ms 65280 KB
subtask_1_43.txt AC 361 ms 73600 KB
subtask_1_44.txt AC 287 ms 65664 KB
subtask_1_45.txt AC 275 ms 67328 KB
subtask_1_46.txt AC 325 ms 68992 KB
subtask_1_47.txt AC 273 ms 64384 KB
subtask_1_48.txt AC 359 ms 72704 KB
subtask_1_49.txt AC 271 ms 65024 KB
subtask_1_50.txt AC 266 ms 66688 KB
subtask_1_51.txt AC 22 ms 61696 KB
subtask_1_52.txt AC 22 ms 63744 KB
subtask_1_53.txt AC 22 ms 63744 KB
subtask_1_54.txt AC 21 ms 61696 KB
subtask_1_55.txt AC 22 ms 63744 KB