Submission #314438

#	Time	Username	Problem	Language	Result	Execution time	Memory
314438		limabeans	Trampoline (info1cup20_trampoline)	C++17	0 / 100	290 ms	103320 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const int inf = 1e9;
const int maxn = 1e6 + 5;


int n,m,t;

map<int,int> vert;
int pt[maxn];




int cc = 0;
vector<int> g[maxn];
map<pair<int,int>,int> mp;
map<int,pair<int,int>> rmp;

vector<int> byrow[maxn];

void addPt(int i, int j) {
    if (mp.count({i,j})) return;
    ++cc;
    mp[{i,j}] = cc;
    rmp[cc] = {i,j};
}


void addEdge(pair<int,int> u, pair<int,int> v) {
    int ui = mp[u];
    int vi = mp[v];

    g[ui].push_back(vi);
    g[vi].push_back(ui);
}


bool solve(int x1, int y1, int x2, int y2) {
    if (x1>x2) return false;
    if (y1>y2) return false;

    auto iter = std::lower_bound(byrow[x1].begin(), byrow[x1].end(), y1);
    if (iter == byrow[x1].end()) {
	return false;
    }

    int c = *iter;
    int at = mp[{x1,c}];
    while (rmp[at].first < x2) {
	//cout<<rmp[at].first<<" "<<rmp[at].second<<endl<<endl;
	
	bool found = false;
	// down
	for (int to: g[at]) {
	    if (rmp[to].first > rmp[at].first) {
		at = to;
		found = true;
		break;
	    }
	}

	if (!found) {
	    // right
	    for (int to: g[at]) {
		if (rmp[to].second > rmp[at].second) {
		    at = to;
		    found = true;
		    break;
		}
	    }
	    if (!found) {
		break;
	    }
	}

	
    }

    if (rmp[at].first != x2) return false;
    return rmp[at].second <= y2;
}

int q;
array<int,4> queries[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>t;
    for (int i=0; i<t; i++) {
	int r,c;
	cin>>r>>c;
	if (!vert.count(r)) vert[r] = inf;
	vert[r] = min(vert[r], c);
    }

    cin>>q;
    for (int i=0; i<q; i++) {
	for (int j=0; j<4; j++) {
	    cin>>queries[i][j];
	}
	byrow[queries[i][0]].push_back(queries[i][1]);
	byrow[queries[i][2]].push_back(queries[i][3]);
    }


    for (int i=1; i<=n; i++) {
	vector<int> &row = byrow[i];
	addPt(i,1);
	row.push_back(1);
	
	if (vert.count(i)) {
	    addPt(i,vert[i]);
	    addPt(i+1,vert[i]);
	    row.push_back(vert[i]);
	    
	    addEdge({i,vert[i]}, {i+1,vert[i]});
	    pt[i+1]=vert[i];
	    
	}
	if (pt[i]) {
	    addPt(i,pt[i]);
	    row.push_back(pt[i]);
	}

	sort(row.begin(),row.end());
	row.erase(unique(row.begin(),row.end()),row.end());

	int len = row.size();
	for (int j=0; j+1<len; j++) {
	    int from=row[j];
	    int to=row[j+1];
	    addEdge({i,from},{i,to});
	}
    }





    for (int i=0; i<q; i++) {
	cout<<(solve(queries[i][0],
		     queries[i][1],
		     queries[i][2],
		     queries[i][3]) ? "Yes\n" : "No\n");
    }    
    
    return 0;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27