oj.uz

Submission #211707

# Submission time Handle Problem Language Result Execution time Memory
211707 2020-03-21T03:52:24 Z nvmdava Sweeping (JOI20_sweeping) C++17
100 / 100
 9400 ms 198756 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 50168 KB Output is correct
2 Correct 47 ms 50168 KB Output is correct
3 Correct 34 ms 50048 KB Output is correct
4 Correct 42 ms 50296 KB Output is correct
5 Correct 34 ms 49920 KB Output is correct
6 Correct 37 ms 50048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7345 ms 196380 KB Output is correct
2 Correct 6473 ms 168392 KB Output is correct
3 Correct 6638 ms 168216 KB Output is correct
4 Correct 4965 ms 166896 KB Output is correct
5 Correct 4597 ms 195872 KB Output is correct
6 Correct 1928 ms 163020 KB Output is correct
7 Correct 7030 ms 168124 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9318 ms 198756 KB Output is correct
2 Correct 8311 ms 182152 KB Output is correct
3 Correct 6318 ms 189316 KB Output is correct
4 Correct 5679 ms 163032 KB Output is correct
5 Correct 7979 ms 178588 KB Output is correct
6 Correct 7996 ms 163372 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 9318 ms 198756 KB Output is correct
2 Correct 8311 ms 182152 KB Output is correct
3 Correct 6318 ms 189316 KB Output is correct
4 Correct 5679 ms 163032 KB Output is correct
5 Correct 7979 ms 178588 KB Output is correct
6 Correct 7996 ms 163372 KB Output is correct
7 Correct 7577 ms 162976 KB Output is correct
8 Correct 7516 ms 163052 KB Output is correct
9 Correct 7336 ms 163064 KB Output is correct
10 Correct 6005 ms 162220 KB Output is correct
11 Correct 5804 ms 162880 KB Output is correct
12 Correct 9400 ms 186936 KB Output is correct
13 Correct 7530 ms 162932 KB Output is correct
14 Correct 166 ms 61432 KB Output is correct
15 Correct 592 ms 105012 KB Output is correct
16 Correct 8333 ms 168068 KB Output is correct
17 Correct 1764 ms 159756 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 50168 KB Output is correct
2 Correct 47 ms 50168 KB Output is correct
3 Correct 34 ms 50048 KB Output is correct
4 Correct 42 ms 50296 KB Output is correct
5 Correct 34 ms 49920 KB Output is correct
6 Correct 37 ms 50048 KB Output is correct
7 Correct 7345 ms 196380 KB Output is correct
8 Correct 6473 ms 168392 KB Output is correct
9 Correct 6638 ms 168216 KB Output is correct
10 Correct 4965 ms 166896 KB Output is correct
11 Correct 4597 ms 195872 KB Output is correct
12 Correct 1928 ms 163020 KB Output is correct
13 Correct 7030 ms 168124 KB Output is correct
14 Correct 9318 ms 198756 KB Output is correct
15 Correct 8311 ms 182152 KB Output is correct
16 Correct 6318 ms 189316 KB Output is correct
17 Correct 5679 ms 163032 KB Output is correct
18 Correct 7979 ms 178588 KB Output is correct
19 Correct 7996 ms 163372 KB Output is correct
20 Correct 7577 ms 162976 KB Output is correct
21 Correct 7516 ms 163052 KB Output is correct
22 Correct 7336 ms 163064 KB Output is correct
23 Correct 6005 ms 162220 KB Output is correct
24 Correct 5804 ms 162880 KB Output is correct
25 Correct 9400 ms 186936 KB Output is correct
26 Correct 7530 ms 162932 KB Output is correct
27 Correct 166 ms 61432 KB Output is correct
28 Correct 592 ms 105012 KB Output is correct
29 Correct 8333 ms 168068 KB Output is correct
30 Correct 1764 ms 159756 KB Output is correct
31 Correct 5398 ms 157876 KB Output is correct
32 Correct 5954 ms 158880 KB Output is correct
33 Correct 6591 ms 165036 KB Output is correct
34 Correct 6914 ms 174612 KB Output is correct
35 Correct 5776 ms 153680 KB Output is correct
36 Correct 5225 ms 160992 KB Output is correct
37 Correct 4853 ms 158276 KB Output is correct
38 Correct 7681 ms 185536 KB Output is correct
39 Correct 6844 ms 161700 KB Output is correct
40 Correct 6512 ms 162052 KB Output is correct