oj.uz

Submission #535954

# Submission time Handle Problem Language Result Execution time Memory
535954 2022-03-11T23:24:52 Z inksamurai Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 1000 ms 15724 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3HspL4A ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class T,class...E>
void print(const T&v,const E&...u){cout<<v<<' ',print(u...);}
// e

using vp=vec(pii);

const int inf=1e9+11;

int cross(int a,int b,int c,int d){
	if(c>=a and c<=b) return 1;
	if(a>=c and a<=d) return 1;
	if(d>=a and d<=b) return 1;
	if(b>=c and b<=d) return 1;
	return 0;
}

signed main(){
_3HspL4A;
	int n;
	cin>>n;
	vp a(n);
	rep(i,n){
		cin>>a[i].fi>>a[i].se;
	}
	
	vi tmp;
	rep(i,n){
		tmp.pb(a[i].fi);
		tmp.pb(a[i].se);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	rep(i,n){
		a[i].fi=lower_bound(tmp.begin(),tmp.end(),a[i].fi)-tmp.begin();
		a[i].se=lower_bound(tmp.begin(),tmp.end(),a[i].se)-tmp.begin();
	}
	const int m=sz(tmp);

	int q;
	cin>>q;
	rep(_,q){
		int s,t;
		cin>>s>>t;
		s-=1;
		int l=a[s].fi,r=a[s].se;
		int cnt=1;
		set<pii> st;
		st.insert({l,r});
		for(int j=s+1;j<t;j++){
			vi c={a[j].fi,a[j].se};
			bool pok=1;
			for(auto v:c){
				auto it=st.lower_bound({v,-inf});
				if(it!=st.end()){
					pii p=*it;
					if(cross(p.fi,p.se,a[j].fi,a[j].se)){
						pok=0;
					}
					auto nit=it;
					nit=next(nit);
					if(nit!=st.end()){
						pii p=*nit;
						if(cross(p.fi,p.se,a[j].fi,a[j].se)){
							pok=0;
						}
					}
				}
				if(it!=st.begin()){
					it=prev(it);
					pii p=*it;
					// if(j==1) print(p.fi,p.se);
					if(cross(p.fi,p.se,a[j].fi,a[j].se)){
						pok=0;
					}	
				}
			}
			if(!pok){
				cnt++;
				st.clear();
			}
			// print(j,pok);
			st.insert({a[j].fi,a[j].se});
		}
		print(cnt);
	}
//	
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:52:12: warning: unused variable 'm' [-Wunused-variable]
   52 |  const int m=sz(tmp);
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 3912 KB Output is correct
2 Correct 143 ms 7544 KB Output is correct
3 Correct 144 ms 7544 KB Output is correct
4 Correct 162 ms 7696 KB Output is correct
5 Correct 149 ms 7892 KB Output is correct
6 Correct 57 ms 7368 KB Output is correct
7 Correct 62 ms 7504 KB Output is correct
8 Correct 65 ms 7396 KB Output is correct
9 Correct 85 ms 7548 KB Output is correct
10 Correct 75 ms 7384 KB Output is correct
11 Correct 268 ms 15724 KB Output is correct
12 Correct 263 ms 14740 KB Output is correct
13 Correct 262 ms 14724 KB Output is correct
14 Correct 215 ms 9384 KB Output is correct
15 Correct 212 ms 8956 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 62 ms 7696 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 472 KB Output is correct
2 Correct 570 ms 720 KB Output is correct
3 Correct 549 ms 604 KB Output is correct
4 Correct 557 ms 712 KB Output is correct
5 Correct 568 ms 736 KB Output is correct
6 Correct 482 ms 740 KB Output is correct
7 Correct 550 ms 596 KB Output is correct
8 Correct 582 ms 724 KB Output is correct
9 Correct 744 ms 720 KB Output is correct
10 Correct 702 ms 712 KB Output is correct
11 Execution timed out 1065 ms 720 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 472 KB Output is correct
2 Correct 570 ms 720 KB Output is correct
3 Correct 549 ms 604 KB Output is correct
4 Correct 557 ms 712 KB Output is correct
5 Correct 568 ms 736 KB Output is correct
6 Correct 482 ms 740 KB Output is correct
7 Correct 550 ms 596 KB Output is correct
8 Correct 582 ms 724 KB Output is correct
9 Correct 744 ms 720 KB Output is correct
10 Correct 702 ms 712 KB Output is correct
11 Execution timed out 1065 ms 720 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 3964 KB Output is correct
2 Correct 570 ms 7736 KB Output is correct
3 Correct 613 ms 7368 KB Output is correct
4 Correct 545 ms 7368 KB Output is correct
5 Correct 610 ms 7496 KB Output is correct
6 Correct 378 ms 7484 KB Output is correct
7 Correct 509 ms 7448 KB Output is correct
8 Correct 500 ms 7364 KB Output is correct
9 Correct 571 ms 7388 KB Output is correct
10 Correct 715 ms 7624 KB Output is correct
11 Execution timed out 1076 ms 13712 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 3912 KB Output is correct
2 Correct 143 ms 7544 KB Output is correct
3 Correct 144 ms 7544 KB Output is correct
4 Correct 162 ms 7696 KB Output is correct
5 Correct 149 ms 7892 KB Output is correct
6 Correct 57 ms 7368 KB Output is correct
7 Correct 62 ms 7504 KB Output is correct
8 Correct 65 ms 7396 KB Output is correct
9 Correct 85 ms 7548 KB Output is correct
10 Correct 75 ms 7384 KB Output is correct
11 Correct 268 ms 15724 KB Output is correct
12 Correct 263 ms 14740 KB Output is correct
13 Correct 262 ms 14724 KB Output is correct
14 Correct 215 ms 9384 KB Output is correct
15 Correct 212 ms 8956 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 62 ms 7696 KB Output is correct
18 Correct 601 ms 472 KB Output is correct
19 Correct 570 ms 720 KB Output is correct
20 Correct 549 ms 604 KB Output is correct
21 Correct 557 ms 712 KB Output is correct
22 Correct 568 ms 736 KB Output is correct
23 Correct 482 ms 740 KB Output is correct
24 Correct 550 ms 596 KB Output is correct
25 Correct 582 ms 724 KB Output is correct
26 Correct 744 ms 720 KB Output is correct
27 Correct 702 ms 712 KB Output is correct
28 Execution timed out 1065 ms 720 KB Time limit exceeded
29 Halted 0 ms 0 KB -