#include <iostream>
#include <cmath>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#define M 1000000007
#define pii pair<int, int>
typedef long long ll;
using namespace std;
/*
vector<vector<int>>vec;
vector<bool>visit;
vector<int>w;
vector<pair<int, pii>>dp1;
vector<pair<int, pii>>dp2;
vector<int>pre;
pair<int,pii> max1(pair<int, pii>a1, pair<int, pii>a2,bool v1,bool v2) {
if (a1.first > a2.first)
return a1;
else if (a1.first < a2.first)
return a2;
else {
if (v1 and !v2)
return a1;
if (v2 and !v1)
return a2;
else {
int tmp1 = abs(a1.second.second - a1.second.first);
int tmp2 = abs(a2.second.second - a2.second.first);
if (tmp1 > tmp2)
return a1;
else if (tmp2 > tmp1)
return a2;
else {
if (a1.second.second > a2.second.second) {
return a1;
}
else if (a2.second.second > a1.second.second)
return a2;
else {
if (a1.second.first > a2.second.first) {
return a2;
}
else if (a2.second.first > a1.second.first)
return a1;
else
return a1;
}
}
}
}
}
vector<bool>he;
void dfs(int v) {
visit[v] = true;
for (int i = 0; i < vec[v].size(); i++) {
if (!visit[vec[v][i]]) {
dfs(vec[v][i]);
}
dp2[v] = max1({ dp1[vec[v][i]].first,{w[v],w[v]} }, dp2[v], true, true);
int val2 = abs(w[vec[v][i]] - w[v]) + dp2[vec[v][i]].first;
int val = dp1[vec[v][i]].second.second - dp1[vec[v][i]].second.first;
int val1 = max(dp1[vec[v][i]].second.second, w[v]) - min(dp1[vec[v][i]].second.first, w[v]);
int val3 = dp1[vec[v][i]].first - val + val1;
bool tmp123 = he[v];
if (val1 > val)
he[v] = true;
else
he[v] = false;
if (val3 >= val2) {
pair<int, pii> a1 = max1({ val3,{min(dp1[vec[v][i]].second.first, w[v]),max(dp1[vec[v][i]].second.second, w[v])} }, dp1[v], he[i], tmp123);
if (dp1[v] != a1 )
pre[v] = vec[v][i];
dp1[v] = a1;
}
else {
pair <int, pii>a1 = max1({ val2,{min(w[vec[v][i]],w[i]),max(w[vec[v][i]],w[i])} }, dp1[v], he[i], tmp123);
if (dp1[v] != a1)
pre[v] = vec[v][i];
dp1[v] = a1;
}
}
}
vector<int>sed;
void bfs(int v) {
vector<bool>visit(vec.size());
vector<int>distance1(vec.size());
distance1[v] = 0;
for (int i = 0; i < vec.size(); i++) {
visit[i] = false;
}
queue<int>queue1;
queue1.push(v);
visit[v] = true;
while (queue1.empty() == false) {
sed.push_back(queue1.front());
int cur = queue1.front();
queue1.pop();
for (int i = 0; i < vec[cur].size(); i++) {
if (visit[vec[cur][i]] == false) {
visit[vec[cur][i]] = true;
distance1[vec[cur][i]] = distance1[cur] + 1;
queue1.push(vec[cur][i]);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
he.resize(n);
pre.resize(n,-1);
w.resize(n);
for (int i = 0; i < n; i++)
cin >> w[i];
vec.resize(n);
visit.resize(n, false);
vector<int>num(n, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
vec[u].push_back(v);
num[u]++;
}
dp1.resize(n, { -1,{-1,-1} });
dp2.resize(n, { -1,{-1,-1} });
for (int i = 0; i < n; i++) {
if (num[i] == 0) {
dp1[i] = { 0,{w[i],w[i]} };
dp2[i] = { 0,{w[i],w[i]} };
visit[i] = true;
}
}
dfs(0);
vector<bool>visit1(n, false);
ll ans = 0;
bfs(0);
for (int i = 0; i < n; i++) {
if (!visit1[sed[i]]) {
ans += dp1[sed[i]].first;
int tmp12 = i;
while (tmp12!=-1) {
visit1[tmp12] = true;
tmp12 = pre[tmp12];
}
}
}
cout << ans;
}*/
/*
int main() {
int n, k;
cin >> n >> k;
multiset<int>set1;
vector<int>vec(n+k);
ll sum = 0;
for (int i = 0; i < n + k; i++) {
cin >> vec[i];
set1.insert(vec[i]);
sum += vec[i];
}
for (int i = 0; i < n + k; i++) {
ll sum1 = sum - vec[i];
set1.erase(set1.find(vec[i]));
auto it = set1.begin();
int a1 = *it;
++it;
int a2 = *it;
int d = a2 - a1;
ll sum2 = (2 * a1 + (n - 1) * d) * n / 2;
if (sum2 == sum1) {
int cnt = 0;
for (int j = 0; j < n + k; j++) {
if (j != i) {
cnt++;
cout << vec[j];
if (cnt != n)
cout << " ";
}
}
break;
}
set1.insert(vec[i]);
}
}*/
#include <map>
vector<int>visit;
int main() {
int n, m, g;
cin >> n >> m >> g;
map<int, set<int>>mp;
vector<int>shor;
vector<pii>gre;
for (int i = 0; i < g; i++) {
int x, y;
cin >> y >> x;
mp[y].insert(x);
shor.push_back(y);
gre.push_back({ y,x });
}
sort(shor.begin(), shor.end());
sort(gre.begin(), gre.end());
int q;
cin >> q;
vector<pii>vec(g);
map<pii, int>con;
for (int i = 0; i < g; i++) {
con[gre[i]] = i;
if (mp[gre[i].first + 1].size() == 0)
vec[i] = { -1, -1 };
else {
auto it = mp[gre[i].first + 1].end();
--it;
if (gre[i].second > * it)
vec[i] = { -1, -1 };
else
vec[i] = { gre[i].first + 1,*mp[gre[i].first + 1].lower_bound(gre[i].second) };
}
}
while (q--) {
int x1, x2, y1, y2;
cin >> y1 >> x1 >> y2 >> x2;
pii st;
if (mp[y1].size() == 0)
st = { -1, -1 };
else {
auto it = mp[y1].end();
--it;
if(x1 > * it)
st = { -1, -1 };
else
st = { y1,*mp[y1].lower_bound(x1) };
}
bool flag = false;
if (y1 == y2 and x1 <= x2)
flag = true;
if (st.first != -1) {
while (!flag) {
if (st.first == y2-1 and st.second <= x2)
flag = true;
else if (vec[con[st]].first == -1)
break;
else if (vec[con[st]].second > x2)
break;
else {
st = vec[con[st]];
}
}
}
if (flag)
cout << "YES";
else
cout << "NO";
cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1456 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
12 ms |
1664 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
10 ms |
1356 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
28220 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
368 ms |
28364 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
1049 ms |
27732 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
1229 ms |
28260 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1054 ms |
38568 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
1075 ms |
38604 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
1051 ms |
38556 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
1116 ms |
38988 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
1107 ms |
38848 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
1181 ms |
44572 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1228 KB |
5000 token(s): yes count is 3238, no count is 1762 |
| 2 |
Correct |
41 ms |
1208 KB |
5000 token(s): yes count is 3837, no count is 1163 |
| 3 |
Correct |
23 ms |
2180 KB |
5000 token(s): yes count is 4104, no count is 896 |
| 4 |
Correct |
31 ms |
1220 KB |
5000 token(s): yes count is 3934, no count is 1066 |
| 5 |
Correct |
522 ms |
1348 KB |
5000 token(s): yes count is 3384, no count is 1616 |
| 6 |
Correct |
22 ms |
1228 KB |
5000 token(s): yes count is 3390, no count is 1610 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
37648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
