Submission #113135

#	Time	Username	Problem	Language	Result	Execution time	Memory
113135		Markomafko972	Plahte (COCI17_plahte)	C++14	0 / 160	410 ms	43532 KiB

plahte

#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;

int w, f;
int n, m;
int a[80002];
int b[80002];
int c[80002];
int d[80002];
map< int, vector< pair<int, int> > > mp;
map< int, vector< pair<int, int> > > :: iterator it;
vector< pair<int, int> > tren;
vector<int> v[80002];
set< pair< pair<int, int>, int> > s;
set< pair< pair<int, int>, int> > :: iterator it2;
bitset<80002> p[80002];
int p1[80002];
int p2[80002];
int p3[80002];
vector<int> saz;
int bio[80002];

void dfs(int x) {
	bio[x] = 1;
	for (int i = 0; i < v[x].size(); i ++) {
		int sus = v[x][i];
		if (bio[sus] == 0) dfs(sus);
		p[x] = p[x]|p[sus];
	}
}

bool cmp(pair<int, int> q1, pair<int, int> q2) {
	if (q1.Y == q2.Y) return q1.X < q2.X;
	if (q1.Y == 0) return 1;
	if (q2.Y == 0) return 0;
	if (q1.Y < 0) return 1;
	if (q2.Y < 0) return 0;
	return 1;
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i ++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		mp[a[i]].push_back({i, 0});
		mp[c[i]].push_back({i, 1});
	}
	
	for (it = mp.begin(); it != mp.end(); it ++) {
		tren = it -> second;
		for (int i = 0; i < tren.size(); i ++) {
			w = tren[i].X;
			f = tren[i].Y;
			
			if (f == 0) {
				it2 = s.lower_bound({{b[w], 0}, 0});
				if (it2 != s.end() && (it2 -> first).Y <= b[w]) {
					v[(it2 -> second)].push_back(w);
				}
				
				s.insert({{d[w], b[w]}, w});
			}
			else {
				s.erase({{d[w], b[w]}, w});
			}
		}
	}
	
	/*for (int i = 0; i < n; i ++) {
		cout << i << ": ";
		for (int j = 0; j < v[i].size(); j ++) cout << v[i][j] << " ";
		cout << endl;
	}*/
	
	for (int i = 0; i < m; i ++) {
		cin >> p1[i] >> p2[i] >> p3[i];
		saz.push_back(p3[i]);
	}
	
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	
	for (int i = 0; i < m; i ++) {
		p3[i] = lower_bound(saz.begin(), saz.end(), p3[i]) - saz.begin();
		p3[i] ++;
		
		mp[ p1[i] ].push_back({i, -p3[i]});
	}
	
	s.clear();
	//cout << "DA" << endl;
	/*for (it = mp.begin(); it != mp.end(); it ++) {
		tren = (it -> second);
		for (int i = 0; i < tren.size(); i ++) {
			if (tren[i].X < 0) {
				cout << "AAAAAAAAAAAAAAAAAAAA";
				return 0;
			}
		}
	}
	
	cout << "Nije";
	return 0;*/
	
	/*cout << mp[22536502][1].X << " " << mp[22536502][1].Y << endl;
	system("pause");*/
	
	for (it = mp.begin(); it != mp.end(); it ++) {
		//cout << (it -> first) << endl;
		tren.clear();
		tren = (it -> second);
		//cout << "2: " << (it -> first) << endl;
		sort(tren.begin(), tren.end(), cmp);
		//cout << (it -> first) << " ," << tren.size() << endl;
		for (int i = 0; i < tren.size(); i ++) {
			//cout << i << endl;
			w = tren[i].X;
			f = tren[i].Y;
			//cout << w << " " << f << endl;
			if (w < 0) {
				continue;
				//cout << w << " RIP";
				//system("pause");
			}
			
			if (f < 0) {
				f *= -1;
				f --;
				it2 = s.lower_bound({{p2[w], 0}, 0});
				if (it2 != s.end() && (it2 -> first).Y <= p2[w]) p[(it2 -> second)][f] = 1;
			}
			else if (f == 0) {
				//cout << "Nula" << endl;
				s.insert({{d[w], b[w]}, w});
				//cout << "Nula2" << endl;
			}
			else {
				//cout << ">0" << endl;
				//cout << "w je " << w << endl;
				it2 = s.find({{d[w], b[w]}, w});
				//cout << "wut" << endl;
				//if (it2 == s.end()) cout << "RIP" << endl;
				s.erase({{d[w], b[w]}, w});
				//cout << ">0 2" << endl;
			}
		}
		
	}
	
	//cout << "DA2" << endl;
	
	for (int i = 0; i < n; i ++) {
		if (bio[i] == 0) dfs(i);
		cout << p[i].count() << endl;
	}

	return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tren.size(); i ++) {
                   ~~^~~~~~~~~~~~~
plahte.cpp:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tren.size(); i ++) {
                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32