oj.uz

Submission #215778

# Submission time Handle Problem Language Result Execution time Memory
215778 2020-03-26T11:28:25 Z tmwilliamlin168 Sweeping (JOI20_sweeping) C++14
100 / 100
 10404 ms 1344360 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;

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

/*
template<class T> struct rmq {
	vector<vector<T>> st;
	vector<int> rank;
	void bld(vector<T> a, vector<int> rk) {
		rank=rk;
//		cout << "rb" << endl;
		int n=a.size();
		st={a};
		for(int k=1; 1<<k<=n; ++k) {
//			cout << k << endl;
			st.push_back(vector<T>(n-(1<<k)+1));
			for(int i=0; i+(1<<k)<=n; ++i)
				st[k][i]=rank[st[k-1][i]]<rank[st[k-1][i+(1<<k-1)]]?st[k-1][i]:st[k-1][i+(1<<k-1)];
		}
	}
	T qry(int l, int r) {
		int k=31-__builtin_clz(r-l+1);
//		return min(st[k][l], st[k][r-(1<<k)+1]);
		return rank[st[k][l]]<rank[st[k][r-(1<<k)+1]]?st[k][l]:st[k][r-(1<<k)+1];
	}
};
*/

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;
//		cout << "rb" << endl;
		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() {
//		cout << "bld" << endl;
		int m=q.size();
		pr=vector<vector<int>>(m);
		set<ar<int, 3>> s;
		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);
		}
//		cout << "hi2" << endl;
		for(ar<int, 3> a : s)
			qs.push_back(a);
//		p=vector<int>(m);
		for(int u : rank)
			dfs(u);
//		assert(p.size()==m);
		rank=vector<int>(m);
		for(int i=0; i<m; ++i) {
			rank[p[i]]=i;
//			cout << q[p[i]][1] << " " << (q[p[i]][1]?q[p[i]][0]:n-q[p[i]][0]) << endl;
		}
//		cout << "hi5" << endl;
		vector<int> sta;
		for(int i=0; i<m; ++i)
			sta.push_back(qs[i][2]);
		rq.bld(sta, rank);
		for(int i=0; i<m; ++i)
			vector<int>().swap(pr[i]);
		vector<vector<int>>().swap(pr);
		vector<int>().swap(sta);
		vector<int>().swap(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:189: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 243 ms 362616 KB Output is correct
2 Correct 234 ms 363112 KB Output is correct
3 Correct 206 ms 361720 KB Output is correct
4 Correct 214 ms 362756 KB Output is correct
5 Correct 235 ms 364116 KB Output is correct
6 Correct 216 ms 363000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6770 ms 770848 KB Output is correct
2 Correct 7278 ms 769960 KB Output is correct
3 Correct 6844 ms 770424 KB Output is correct
4 Correct 4802 ms 767316 KB Output is correct
5 Correct 5082 ms 782104 KB Output is correct
6 Correct 6967 ms 770404 KB Output is correct
7 Correct 7791 ms 770428 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7149 ms 850076 KB Output is correct
2 Correct 7161 ms 850056 KB Output is correct
3 Correct 5694 ms 849536 KB Output is correct
4 Correct 6456 ms 854188 KB Output is correct
5 Correct 7719 ms 850060 KB Output is correct
6 Correct 8224 ms 850108 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7149 ms 850076 KB Output is correct
2 Correct 7161 ms 850056 KB Output is correct
3 Correct 5694 ms 849536 KB Output is correct
4 Correct 6456 ms 854188 KB Output is correct
5 Correct 7719 ms 850060 KB Output is correct
6 Correct 8224 ms 850108 KB Output is correct
7 Correct 6917 ms 850312 KB Output is correct
8 Correct 7004 ms 850304 KB Output is correct
9 Correct 6892 ms 850308 KB Output is correct
10 Correct 5483 ms 849668 KB Output is correct
11 Correct 6292 ms 854172 KB Output is correct
12 Correct 7105 ms 850192 KB Output is correct
13 Correct 7615 ms 850324 KB Output is correct
14 Correct 10404 ms 1344360 KB Output is correct
15 Correct 672 ms 381304 KB Output is correct
16 Correct 7587 ms 850176 KB Output is correct
17 Correct 7111 ms 850168 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 362616 KB Output is correct
2 Correct 234 ms 363112 KB Output is correct
3 Correct 206 ms 361720 KB Output is correct
4 Correct 214 ms 362756 KB Output is correct
5 Correct 235 ms 364116 KB Output is correct
6 Correct 216 ms 363000 KB Output is correct
7 Correct 6770 ms 770848 KB Output is correct
8 Correct 7278 ms 769960 KB Output is correct
9 Correct 6844 ms 770424 KB Output is correct
10 Correct 4802 ms 767316 KB Output is correct
11 Correct 5082 ms 782104 KB Output is correct
12 Correct 6967 ms 770404 KB Output is correct
13 Correct 7791 ms 770428 KB Output is correct
14 Correct 7149 ms 850076 KB Output is correct
15 Correct 7161 ms 850056 KB Output is correct
16 Correct 5694 ms 849536 KB Output is correct
17 Correct 6456 ms 854188 KB Output is correct
18 Correct 7719 ms 850060 KB Output is correct
19 Correct 8224 ms 850108 KB Output is correct
20 Correct 6917 ms 850312 KB Output is correct
21 Correct 7004 ms 850304 KB Output is correct
22 Correct 6892 ms 850308 KB Output is correct
23 Correct 5483 ms 849668 KB Output is correct
24 Correct 6292 ms 854172 KB Output is correct
25 Correct 7105 ms 850192 KB Output is correct
26 Correct 7615 ms 850324 KB Output is correct
27 Correct 10404 ms 1344360 KB Output is correct
28 Correct 672 ms 381304 KB Output is correct
29 Correct 7587 ms 850176 KB Output is correct
30 Correct 7111 ms 850168 KB Output is correct
31 Correct 5578 ms 790264 KB Output is correct
32 Correct 6151 ms 790136 KB Output is correct
33 Correct 5776 ms 790136 KB Output is correct
34 Correct 5930 ms 791800 KB Output is correct
35 Correct 6082 ms 791672 KB Output is correct
36 Correct 5195 ms 787320 KB Output is correct
37 Correct 5824 ms 799112 KB Output is correct
38 Correct 6957 ms 790520 KB Output is correct
39 Correct 6893 ms 790392 KB Output is correct
40 Correct 6603 ms 790780 KB Output is correct