oj.uz

Submission #314437

# Submission time Handle Problem Language Result Execution time Memory
314437 2020-10-19T22:55:06 Z limabeans Trampoline (info1cup20_trampoline) C++17
0 / 100
 257 ms 107384 KB 
#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;
	    }
	}

	// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 47608 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 51192 KB expected YES, found NO [3rd token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 99916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 95864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 107384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -