Submission #211707

#	Time	Username	Problem	Language	Result	Execution time	Memory
211707		nvmdava	Sweeping (JOI20_sweeping)	C++17	100 / 100	9400 ms	198756 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 2100000
#define MOD 998244353
#define INF 0x3f3f3f3f

int x[N], y[N], s[N], ox[N], oy[N];
int n, m, q;

struct Query{
	int id, l, r, ax = -1, ay = -1;
	Query(int _id, int _l, int _r){
		id = _id; l = _l; r = _r;
	}
};

vector<Query> query;

int ans[N];

int upd[N][2];

vector<int> segquery[N];

void insert(int id, int l, int r, int L, int R, int v){
	if(l > R || r < L) return;
	if(L <= l && r <= R){
		segquery[id].push_back(v);
		return;
	}
	int m = (l + r) >> 1;
	insert(id << 1, l, m, L, R, v);
	insert(id << 1 | 1, m + 1, r, L, R, v);
}

map<pair<int, int>, pair<int, int> > c2;
map<int, pair<int, int> > c1;
vector<pair<pair<int, int>, pair<int, int> > > wtf;
void solve(int id, int l, int r){
	if(l != r){
		int m = (l + r) >> 1;
		solve(id << 1, l, m);
		solve(id << 1 | 1, m + 1, r);
	}
	if(segquery[id].empty()) return;
	c1.clear();
	c2.clear();
	wtf.clear();

	c2[{n, n}] = {0, 0};
	
	for(int i = l; i <= r; ++i){
		int xx = n - upd[i][1];
		int yy = upd[i][1];
		if(upd[i][0])
			swap(xx, yy);
		auto it = c2.lower_bound({xx, yy});
		int x1, y1, x2, y2;
		x1 = it -> ss.ff;
		y1 = it -> ss.ss;
		x2 = it -> ff.ff;
		y2 = it -> ff.ss;
		if((upd[i][0] == 0 && yy == y2) || (upd[i][0] == 1 && xx == x2)) continue;
		c2.erase({x2, y2});
		if(upd[i][0] == 0){
			c2[{x2, yy}] = {x1, y1};
			c2[{xx - 1, y2}] = {x1, yy + 1};
		} else {
			c2[{xx, y2}] = {x1, y1};
			c2[{x2, yy - 1}] = {xx + 1, y1};
		}
	}
	

	for(auto& a : c2)
		wtf.push_back(a);
	
	sort(wtf.begin(), wtf.end(), [](const pair<pair<int, int>, pair<int, int> >& lhs, const pair<pair<int, int>, pair<int, int> >& rhs){
		return lhs.ss.ff < rhs.ss.ff;
	});
	sort(segquery[id].begin(), segquery[id].end(), [](const int& lhs, const int& rhs){
		return x[query[lhs].id] < x[query[rhs].id];
	});

	int sz = wtf.size();
	int j = 0;

	for(auto& a : segquery[id]){
		int i = query[a].id;
		while(j < sz && wtf[j].ss.ff <= x[i]){
			c1[wtf[j].ss.ss] = wtf[j].ff;
			++j;
		}
		auto it = --c1.upper_bound(y[i]);
		query[a].ax = x[i] = max(x[i], n - it -> ss.ss);
		query[a].ay = y[i] = max(y[i], n - it -> ss.ff);
	}
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int qq;
    cin>>n>>m>>qq;
    for(int i = 1; i <= m; ++i){
    	cin>>x[i]>>y[i];
    	ox[i] = x[i];
    	oy[i] = y[i];
    	s[i] = 1;
    }

    while(qq--){
    	int t;
    	cin>>t;
    	if(t == 1){
    		int i;
    		cin>>i;
    		query.push_back(Query(i, s[i], q));
    		s[i] = q + 1;
    	} else if(t == 4){
    		++m;
    		s[m] = q + 1;
    		cin>>x[m]>>y[m];
    		ox[m] = x[m];
    		oy[m] = y[m];
    	} else {
    		++q;
    		upd[q][0] = t - 2;
    		cin>>upd[q][1];
    	}
    }
    if(q){
	    for(int i = 0; i < query.size(); ++i){
	    	if(query[i].l <= query[i].r){
	    		insert(1, 1, q, query[i].l, query[i].r, i);
	    	}
	    }

	    solve(1, 1, q);
    }

    for(auto& a : query){
    	if(a.ax != -1){
    		ox[a.id] = a.ax;
    		oy[a.id] = a.ay;
    	}
    	cout<<ox[a.id]<<' '<<oy[a.id]<<'\n';
    }
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < query.size(); ++i){
                     ~~^~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25