oj.uz

Submission #215505

# Submission time Handle Problem Language Result Execution time Memory
215505 2020-03-26T11:21:14 Z tmwilliamlin168 Sweeping (JOI20_sweeping) C++14
22 / 100
 9479 ms 2097156 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxM=5e5, mxQ=1e6;
int n, m, q, no;
vector<ar<int, 3>> v;
set<ar<int, 3>> s;

void pr(ar<int, 2> &a, int l, int t) {
	if(a[t^1]<=l&&a[t]<n-l)
		a[t]=n-l;
}

struct rmq {
	int n;
	vector<int> st;
	vector<int> rank;
	int mn(int a, int b) {
		if(b==-1)
			return a;
		return rank[a]<rank[b]?a:b;
	}
	void bld(vector<int> a, vector<int> rk) {
		rank=rk;
		n=a.size();
		st=vector<int>(2*n);
		for(int i=0; i<n; ++i)
			st[i+n]=a[i];
		for(int i=n-1; i; --i)
			st[i]=mn(st[2*i], st[2*i+1]);
	}
	int qry(int l, int r) {
		int b=-1;
		for(l+=n, r+=n+1; l<r; ++l/=2, r/=2) {
			if(l&1)
				b=mn(st[l], b);
			if(r&1)
				b=mn(st[r-1], b);
		}
		return b;
	}
};

struct node {
	vector<ar<int, 3>> q, qs;
	rmq rq;
	vector<vector<int>> pr;
	vector<int> p, rank;
	void dfs(int u) {
		for(int v : pr[u])
			dfs(v);
		p.push_back(u);
	}
	void bld() {
		int m=q.size();
		pr=vector<vector<int>>(m);
		for(ar<int, 3> a : q) {
			auto it=s.lower_bound(a), it2=it;
			bool hp=0;
			if(it!=s.end()) {
				//type 1
				if(a[1]==1&&(*it)[1]==1) {
					pr[(*it)[2]].push_back(a[2]);
					hp=1;
				}
			}
			it=it2;
			if(it!=s.begin()) {
				--it;
				//type 0
				if(a[1]==0&&(*it)[1]==0) {
					pr[(*it)[2]].push_back(a[2]);
					hp=1;
				}
			}
			if(!hp)
				rank.push_back(a[2]);
			s.insert(a);
		}
		for(ar<int, 3> a : s)
			qs.push_back(a);
		s.clear();
		for(int u : rank)
			dfs(u);
		rank=vector<int>(m);
		for(int i=0; i<m; ++i)
			rank[p[i]]=i;
		vector<int> sta;
		for(int i=0; i<m; ++i)
			sta.push_back(qs[i][2]);
		rq.bld(sta, rank);
	}
	void app(ar<int, 2> &a) {
		int l=lower_bound(qs.begin(), qs.end(), ar<int, 3>{a[0]})-qs.begin(), r=lower_bound(qs.begin(), qs.end(), ar<int, 3>{n-a[1]+1})-qs.begin()-1;
		if(l>r)
			return;
		int qi=rq.qry(l, r), p=lower_bound(qs.begin(), qs.end(), q[qi])-qs.begin();
		::pr(a, q[qi][1]?q[qi][0]:n-q[qi][0], q[qi][1]);
		if(q[qi][1]) {
			//vertical, then horizontal
			if(l>p-1)
				return;
			r=p-1;
		} else {
			//horizontal, then vertical
			if(p+1>r)
				return;
			l=p+1;
		}
		qi=rq.qry(l, r);
		::pr(a, q[qi][1]?q[qi][0]:n-q[qi][0], q[qi][1]);
	}
} st[1<<21];

void qry(ar<int, 2> &a, int l1, int r1, int i=1, int l2=0, int r2=(1<<20)-1) {
	if(l1<=l2&&r2<=r1) {
		st[i].app(a);
		return;
	}
	int m2=(l2+r2)/2;
	if(l1<=m2)
		qry(a, l1, r1, 2*i, l2, m2);
	if(m2<r1)
		qry(a, l1, r1, 2*i+1, m2+1, r2);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	v=vector<ar<int, 3>>(m);
	for(int i=0; i<m; ++i)
		cin >> v[i][0] >> v[i][1];
	while(q--) {
		int qt;
		cin >> qt;
		if(qt==1) {
			int p;
			cin >> p, --p;
			ar<int, 2> a{v[p][0], v[p][1]};
			if(no)
				qry(a, v[p][2], no-1);
			cout << a[0] << " " << a[1] << "\n";
		} else if(qt==2||qt==3) {
			int l;
			cin >> l;
			int u=no+(1<<20);
			while(u) {
				st[u].q.push_back({qt&1?l:n-l, qt-2, st[u].q.size()});
				u/=2;
			}
			u=no+(1<<20);
			while(1) {
				st[u].bld();
				if((u+1)&1)
					break;
				u/=2;
			}
			++no;
		} else if(qt==4) {
			int a, b;
			cin >> a >> b;
			v.push_back({a, b, no});
		}
	}
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:152:54: warning: narrowing conversion of 'st[u].node::q.std::vector<std::array<int, 3> >::size()' from 'std::vector<std::array<int, 3> >::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
     st[u].q.push_back({qt&1?l:n-l, qt-2, st[u].q.size()});
                                          ~~~~~~~~~~~~^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 363128 KB Output is correct
2 Correct 209 ms 363908 KB Output is correct
3 Correct 219 ms 361720 KB Output is correct
4 Correct 232 ms 363128 KB Output is correct
5 Correct 221 ms 365432 KB Output is correct
6 Correct 214 ms 364024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8095 ms 1104908 KB Output is correct
2 Correct 8045 ms 1091848 KB Output is correct
3 Correct 8284 ms 1103884 KB Output is correct
4 Correct 4840 ms 992336 KB Output is correct
5 Correct 5969 ms 1210888 KB Output is correct
6 Correct 8214 ms 1103252 KB Output is correct
7 Correct 8953 ms 1103112 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8600 ms 1230236 KB Output is correct
2 Correct 8399 ms 1220288 KB Output is correct
3 Correct 6221 ms 1133640 KB Output is correct
4 Correct 7853 ms 1379496 KB Output is correct
5 Correct 9326 ms 1235228 KB Output is correct
6 Correct 8991 ms 1219192 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 8600 ms 1230236 KB Output is correct
2 Correct 8399 ms 1220288 KB Output is correct
3 Correct 6221 ms 1133640 KB Output is correct
4 Correct 7853 ms 1379496 KB Output is correct
5 Correct 9326 ms 1235228 KB Output is correct
6 Correct 8991 ms 1219192 KB Output is correct
7 Correct 8748 ms 1219600 KB Output is correct
8 Correct 8887 ms 1220000 KB Output is correct
9 Correct 8226 ms 1220436 KB Output is correct
10 Correct 6084 ms 1133684 KB Output is correct
11 Correct 8220 ms 1379648 KB Output is correct
12 Correct 8969 ms 1219120 KB Output is correct
13 Correct 8903 ms 1219396 KB Output is correct
14 Runtime error 9479 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 363128 KB Output is correct
2 Correct 209 ms 363908 KB Output is correct
3 Correct 219 ms 361720 KB Output is correct
4 Correct 232 ms 363128 KB Output is correct
5 Correct 221 ms 365432 KB Output is correct
6 Correct 214 ms 364024 KB Output is correct
7 Correct 8095 ms 1104908 KB Output is correct
8 Correct 8045 ms 1091848 KB Output is correct
9 Correct 8284 ms 1103884 KB Output is correct
10 Correct 4840 ms 992336 KB Output is correct
11 Correct 5969 ms 1210888 KB Output is correct
12 Correct 8214 ms 1103252 KB Output is correct
13 Correct 8953 ms 1103112 KB Output is correct
14 Correct 8600 ms 1230236 KB Output is correct
15 Correct 8399 ms 1220288 KB Output is correct
16 Correct 6221 ms 1133640 KB Output is correct
17 Correct 7853 ms 1379496 KB Output is correct
18 Correct 9326 ms 1235228 KB Output is correct
19 Correct 8991 ms 1219192 KB Output is correct
20 Correct 8748 ms 1219600 KB Output is correct
21 Correct 8887 ms 1220000 KB Output is correct
22 Correct 8226 ms 1220436 KB Output is correct
23 Correct 6084 ms 1133684 KB Output is correct
24 Correct 8220 ms 1379648 KB Output is correct
25 Correct 8969 ms 1219120 KB Output is correct
26 Correct 8903 ms 1219396 KB Output is correct
27 Runtime error 9479 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -