Submission #113101

#	Time	Username	Problem	Language	Result	Execution time	Memory
113101		Markomafko972	Plahte (COCI17_plahte)	C++14	0 / 160	421 ms	75120 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 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<1002> 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 == 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 ++) {
			int w = tren[i].X;
			int 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]});
	}
	
	for (it = mp.begin(); it != mp.end(); it ++) {
		tren = it -> second;
		sort(tren.begin(), tren.end(), cmp);
		for (int i = 0; i < tren.size(); i ++) {
			int w = tren[i].X;
			int f = tren[i].Y;
			
			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) {
				s.insert({{d[w], b[w]}, w});
			}
			else {
				s.erase({{d[w], b[w]}, w});
			}
		}
	}
	
	
	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:30: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:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tren.size(); i ++) {
                   ~~^~~~~~~~~~~~~
plahte.cpp:100: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