Submission #110172

#	Time	Username	Problem	Language	Result	Execution time	Memory
110172		tincamatei	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	512 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int MOD = 1000000007;

int box[1+2*MAX_N];
int color[1+MAX_N], last[1+MAX_N];

set<pair<int, int> > emp, c[3];

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, rez = 1;
	fscanf(fin, "%d", &n);

	for(int i = 1; i <= n; ++i) {
		int a, b;
		fscanf(fin, "%d%d", &a, &b);
		box[a] = i;
		box[b] = -i;
		last[i] = a;
	}

	for(int i = 1; i <= 2 * n; ++i) {
		set<pair<int, int> >::iterator it;

		if(box[i] > 0) {
			emp.insert(make_pair(last[box[i]], box[i]));
		} else {
			box[i] = -box[i];
			
			if(color[box[i]] == 0) {
				if(c[1].lower_bound(make_pair(last[box[i]] + 1, -1)) != c[1].end())
					color[box[i]] = 2;
				else if(c[2].lower_bound(make_pair(last[box[i]] + 1, -1)) != c[2].end())
					color[box[i]] = 1;
				else {
					rez = rez * 2 % MOD;
					color[box[i]] = 1;
				}
			}

			it = emp.lower_bound(make_pair(last[box[i]] + 1, -1));
			while(it != emp.end()) {
				color[it->second] = 3 - color[box[i]];
				c[color[it->second]].insert(*it);
				it = emp.erase(it);
			}
			it = c[color[box[i]]].lower_bound(make_pair(last[box[i]] + 1, -1));
			if(it != c[color[box[i]]].end()) {
				rez = 0;
			}
			
			emp.erase(make_pair(last[box[i]], box[i]));
			c[color[box[i]]].erase(make_pair(last[box[i]], box[i]));
		}
	}

	fprintf(fout, "%d", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:23:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
port_facility.cpp:27:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22