Submission #595242

#	Time	Username	Problem	Language	Result	Execution time	Memory
595242		FatihSolak	Seats (IOI18_seats)	C++17	31 / 100	4096 ms	247136 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
set<int> sr[N],sc[N];
vector<int> r,c;
int h,w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H;
	w = W;
	r = R;
	c = C;
	for(int i = 0;i<h*w;i++){
		sr[r[i]].insert(i+1);
		sc[c[i]].insert(i+1);
	}
}

int swap_seats(int a, int b) {
	if(a > b)swap(a,b);
	sr[r[a]].erase(a+1);
	sc[c[a]].erase(a+1);

	sr[r[b]].erase(b+1);
	sc[c[b]].erase(b+1);


	swap(r[a],r[b]);
	swap(c[a],c[b]);

	sr[r[a]].insert(a+1);
	sc[c[a]].insert(a+1);

	sr[r[b]].insert(b+1);
	sc[c[b]].insert(b+1);



	vector<pair<int,int>> rlen,clen;

	vector<pair<int,int>> stdec,stinc;

	for(int i = h-1;i>=0;i--){
		int num = *sr[i].begin();
		while(stdec.size() && stdec.back().first > num){
			stdec.pop_back();
		}
		stdec.push_back({num,i});
	}
	for(int i = 0;i<h;i++){
		int num = *sr[i].begin();
		while(stinc.size() && stinc.back().first > num){
			stinc.pop_back();
		}
		stinc.push_back({num,i});
	}

	// cout << "stdec: " << endl;
	// for(auto u:stdec){
	// 	cout << u.first << " " << u.second << endl;
	// }
	// cout << "stinc: " << endl;
	// for(auto u:stinc){
	// 	cout << u.first << " " << u.second << endl;
	// }
	int pt1 = 0,pt2 = 0;
	rlen.push_back({1,stinc[pt2].second - stdec[pt1].second + 1});
	while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
		if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
			pt2++;
			rlen.push_back({stinc[pt2].first,stinc[pt2].second - stdec[pt1].second + 1});
		}
		else{
			pt1++;
			rlen.push_back({stdec[pt1].first,stinc[pt2].second - stdec[pt1].second + 1});
		}
	}


	stdec.clear(),stinc.clear();

	for(int i = w-1;i>=0;i--){
		int num = *sc[i].begin();
		while(stdec.size() && stdec.back().first > num){
			stdec.pop_back();
		}
		stdec.push_back({num,i});
	}
	for(int i = 0;i<w;i++){
		int num = *sc[i].begin();
		while(stinc.size() && stinc.back().first > num){
			stinc.pop_back();
		}
		stinc.push_back({num,i});
	}


	pt1 = 0,pt2 = 0;
	clen.push_back({1,stinc[pt2].second - stdec[pt1].second + 1});
	while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
		if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
			pt2++;
			clen.push_back({stinc[pt2].first,stinc[pt2].second - stdec[pt1].second + 1});
		}
		else{
			pt1++;
			clen.push_back({stdec[pt1].first,stinc[pt2].second - stdec[pt1].second + 1});
		}
	}


	// cout << "hey" << endl;
	// for(auto u:rlen){
	// 	cout << u.first << " " << u.second << endl;
	// }
	// cout << endl;
	// for(auto u:clen){
	// 	cout << u.first << " " << u.second << endl;
	// }
	//cout << "hey" << endl;


	int ans = 0;
	for(int i = 0;i<rlen.size();i++){
		int l = rlen[i].first,r = h*w;
		if(i + 1 != rlen.size())
			r = rlen[i+1].first - 1;
		int pos = (l + rlen[i].second-1) / rlen[i].second * rlen[i].second;
		while(pos <= r){
			int len = pos / rlen[i].second;
			//cout << rlen[i].first << " " << rlen[i].second << " " << pos << " " << len << endl;

			if(prev(upper_bound(clen.begin(),clen.end(),make_pair(pos+1,0)))->second == len)
				ans++;

			pos += rlen[i].second;
		}
	}
	return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
      |        ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:68:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
      |      ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:69:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
      |        ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:100:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  while(pt1 + 1 != stdec.size() || pt2 + 1 != stinc.size()){
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:101:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
      |      ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:101:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if(pt1 + 1 == stdec.size() || (pt2 + 1 != stinc.size() &&  stdec[pt1+1].first > stinc[pt2+1].first)){
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~
seats.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i = 0;i<rlen.size();i++){
      |                ~^~~~~~~~~~~~
seats.cpp:126:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   if(i + 1 != rlen.size())
      |      ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30