Submission #736473

#	Time	Username	Problem	Language	Result	Execution time	Memory
736473		myrcella	Seats (IOI18_seats)	C++17	25 / 100	1774 ms	133956 KiB

seats

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "seats.h"
const int maxn = 1e3+10;
int n;
int h,w;
pii pos[maxn*maxn];
set <int> r[maxn],c[maxn];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  rep(i,0,H*W) pos[i] = {R[i],C[i]}, r[R[i]].insert(i),c[C[i]].insert(i);
  n = H*W;
  h  = H, w=W;
}

int swap_seats(int a, int b) {
	int ret = 0;
	r[pos[a].fi].erase(a),c[pos[a].se].erase(a);
	r[pos[b].fi].erase(b),c[pos[b].se].erase(b);
	swap(pos[a],pos[b]);
	r[pos[a].fi].insert(a),c[pos[a].se].insert(a);
	r[pos[b].fi].insert(b),c[pos[b].se].insert(b);
	vector <pii> minx,maxx,miny,maxy;
	rep(i,0,h) {
		int cur = (*r[i].begin()); //first appearance of row i
		while (!maxx.empty() and maxx.back().fi > cur) maxx.pop_back();
		maxx.pb({cur,i});
	}
	for (int i=h-1;i>=0;i--) {
		int cur = (*r[i].begin());
		while (!minx.empty() and minx.back().fi > cur) minx.pop_back();
		minx.pb({cur,i});
	}
	rep(i,0,w) {
		int cur = (*c[i].begin()); //first appearance of row i
		while (!maxy.empty() and maxy.back().fi > cur) maxy.pop_back();
		maxy.pb({cur,i});
	}
	for (int i=w-1;i>=0;i--) {
		int cur = (*c[i].begin());
		while (!miny.empty() and miny.back().fi > cur) miny.pop_back();
		miny.pb({cur,i});
	}
	reverse(ALL(minx));reverse(ALL(miny));reverse(ALL(maxx));reverse(ALL(maxy));
	int lst = -1,lstarea=-233;
	int val0,val1,val2,val3;
	while (SZ(minx)+SZ(miny)+SZ(maxx)+SZ(maxy)>0) {
		int cur = mod;
		if (!minx.empty()) cur = min(cur,minx.back().fi);
		if (!miny.empty()) cur = min(cur,miny.back().fi);
		if (!maxx.empty()) cur = min(cur,maxx.back().fi);
		if (!maxy.empty()) cur = min(cur,maxy.back().fi);
//		debug(cur);
		if (lstarea>=lst and lstarea<cur) ret++;
		
		if (!minx.empty() and minx.back().fi==cur) val0 = minx.back().se,minx.pop_back();
		if (!maxx.empty() and maxx.back().fi==cur) val1 = maxx.back().se,maxx.pop_back();	
		if (!miny.empty() and miny.back().fi==cur) val2 = miny.back().se,miny.pop_back();
		if (!maxy.empty() and maxy.back().fi==cur) val3 = maxy.back().se,maxy.pop_back();
		
		lstarea = (val1-val0+1)*(val3-val2+1)-1;
		lst = cur;
	}
	if (lstarea>=lst and lstarea<n) ret++;
  return ret;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:82:32: warning: 'val3' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   lstarea = (val1-val0+1)*(val3-val2+1)-1;
      |                            ~~~~^~~~~
seats.cpp:82:32: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
seats.cpp:82:18: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   lstarea = (val1-val0+1)*(val3-val2+1)-1;
      |              ~~~~^~~~~
seats.cpp:82:18: warning: 'val0' may be used uninitialized in this function [-Wmaybe-uninitialized]

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