oj.uz

답안 #339684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339684 2020-12-25T23:14:38 Z wwdd Trampoline (info1cup20_trampoline) C++14
0 / 100
 2000 ms 7648 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const int MN = 200200;
const int LOG = 20;
ll nx[MN][LOG];
struct Q {
	ll id;
	pl st,ed;
	bool operator< (const Q& other)  {
		return st.second < other.st.second;
	}
};
vector<Q> qu;
vector<pl> tr;
map<ll,ll> mu;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll mr,mc;
	cin >> mr >> mc;
	ll n,N;
	cin >> n;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		tr.emplace_back(a,b);
	}
	sort(tr.begin(),tr.end(),[&](const pl& a, const pl& b){
			if(a.second > b.second) {return true;}
			return a.first > b.first;
			});
	cin >> N;
	vector<ll> ans(N,0);
	for(int i=0;i<N;i++) {
		ll sr,sc,tr,tc;
		cin >> sr >> sc >> tr >> tc;
		qu.push_back({i,{sr,sc},{tr,tc}});
	}
	ll trp = 0;
	sort(qu.begin(),qu.end());
	for(int i=N-1;i>=0;i--) {
		Q q = qu[i];
		while(trp < tr.size() && tr[trp].second >= q.st.second) {
			ll r = tr[trp].first;
			mu[r] = trp;
			if(mu.count(r+1)) {
				nx[trp][0] = mu[r+1];
			} else {
				nx[trp][0] = trp;
			}
			for(int i=1;i<LOG;i++) {
				nx[trp][i] = nx[nx[trp][i-1]][i-1];
			}
			trp++;
		}
		ll idx = q.id;
		if(q.st.first == q.ed.first) {
			if(q.st.second <= q.ed.second)  {
				ans[idx] = 1;
			} else {
				ans[idx] = 0;
			}
		} else if(!mu.count(q.st.first)) {
				ans[idx] = 0;
		} else {
			ll no = mu[q.st.first];
			ll dif = q.ed.first-q.st.first-1;
			if(dif < 0) {ans[idx] = 0;} else {
				for(int i=LOG-1;i>=0;i--) {
					if(dif&(1<<i)) {
						no = nx[no][i];
					}
				}
			}
			if(tr[no].first+1 == q.ed.first && tr[no].second <= q.ed.second) {
				ans[idx] = 1;
			} else {
				ans[idx] = 0;
			}
		}
	}
	for(int i=0;i<N;i++) {
		cout << (ans[i]?"Yes":"No") << '\n';
	}
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:44:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   while(trp < tr.size() && tr[trp].second >= q.st.second) {
      |         ~~~~^~~~~~~~~~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 1136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2095 ms 5988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 5860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 1992 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 7648 KB Time limit exceeded
2 Halted 0 ms 0 KB -