| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 919612 | 2024-02-01T08:49:32 Z | andrei_iorgulescu | Trampoline (info1cup20_trampoline) | C++14 | 1137 ms | 62136 KB |
#include <bits/stdc++.h>
using namespace std;
int r,c,n,q;
int x[200005],y[200005];
map<int,vector<pair<int,int>>>v;
int jump[20][200005];
set<int>st;
int lg[200005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];
v[x[i]].push_back({y[i],i});
st.insert(x[i]);
}
for (auto it : st)
sort(v[it].begin(),v[it].end());
for (int i = 1; i <= n; i++)
{
int xx = x[i] + 1,yy = y[i];
int st = -1,pas = 1 << 17;
while (pas != 0)
{
if (st + pas < v[xx].size() and v[xx][st + pas].first < yy)
st += pas;
pas /= 2;
}
st++;
if (st == v[xx].size())
jump[0][i] = -1;
else
jump[0][i] = v[xx][st].second;
}
for (int i = 2; i <= n; i++)
lg[i] = 1 + lg[i / 2];
for (int b = 1; b <= lg[n]; b++)
{
for (int i = 1; i <= n; i++)
{
if (jump[b - 1][i] == -1)
jump[b][i] = -1;
else
jump[b][i] = jump[b - 1][jump[b - 1][i]];
}
}
cin >> q;
for (int i = 1; i <= q; i++)
{
int xs,ys,xf,yf;
cin >> xs >> ys >> xf >> yf;
if (xs > xf or ys > yf)
cout << "No\n";
else if (xs == xf)
cout << "Yes\n";
else
{
int xx = xs,yy = ys;
int st = -1,pas = 1 << 17;
//cout << yy << ' ' << v[xx][0].first << '\n';
while (pas != 0)
{
if (st + pas < v[xx].size() and v[xx][st + pas].first < yy)
st += pas;
pas /= 2;
}
st++;
//cout << st << ' ';
if (st == v[xx].size())
cout << "No\n";
else
{
int tr = v[xx][st].second;
if (y[tr] > yf)
cout << "No\n";
else
{
//cout << tr << ' ';
for (int b = lg[n]; b >= 0; b--)
{
//cout << jump[b][tr] << ' ';
if (jump[b][tr] != -1 and y[jump[b][tr]] <= yf)
tr = jump[b][tr];
}
if (x[tr] + 1 >= xf)
cout << "Yes\n";
else
cout << "No\n";
}
}
}
}
return 0;
}
/**
next[i] = care e urmatoarea verde in care as merge din trambulina i
fac binary lifting pe treaba asta
vad in ce trambulina verde urc si daca pe jumpurile aleia ajung la linia xf inainte de yf
**/
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 14936 KB | 200 token(s): yes count is 21, no count is 179 |
| 2 | Correct | 9 ms | 14936 KB | 200 token(s): yes count is 70, no count is 130 |
| 3 | Correct | 7 ms | 12892 KB | 197 token(s): yes count is 25, no count is 172 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 265 ms | 21584 KB | 4000 token(s): yes count is 99, no count is 3901 |
| 2 | Correct | 259 ms | 21584 KB | 4000 token(s): yes count is 91, no count is 3909 |
| 3 | Correct | 204 ms | 20624 KB | 4000 token(s): yes count is 4000, no count is 0 |
| 4 | Correct | 278 ms | 21408 KB | 4000 token(s): yes count is 1991, no count is 2009 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 210 ms | 21192 KB | 200000 token(s): yes count is 110486, no count is 89514 |
| 2 | Correct | 234 ms | 32764 KB | 200000 token(s): yes count is 114664, no count is 85336 |
| 3 | Correct | 284 ms | 32848 KB | 200000 token(s): yes count is 86232, no count is 113768 |
| 4 | Correct | 587 ms | 33696 KB | 200000 token(s): yes count is 94603, no count is 105397 |
| 5 | Correct | 616 ms | 33756 KB | 200000 token(s): yes count is 94148, no count is 105852 |
| 6 | Correct | 831 ms | 42320 KB | 200000 token(s): yes count is 97163, no count is 102837 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 12888 KB | 5000 token(s): yes count is 3238, no count is 1762 |
| 2 | Correct | 8 ms | 13148 KB | 5000 token(s): yes count is 3837, no count is 1163 |
| 3 | Correct | 14 ms | 14172 KB | 5000 token(s): yes count is 4104, no count is 896 |
| 4 | Correct | 6 ms | 13148 KB | 5000 token(s): yes count is 3934, no count is 1066 |
| 5 | Correct | 14 ms | 13404 KB | 5000 token(s): yes count is 3384, no count is 1616 |
| 6 | Correct | 6 ms | 13148 KB | 5000 token(s): yes count is 3390, no count is 1610 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 910 ms | 32848 KB | 200000 token(s): yes count is 171404, no count is 28596 |
| 2 | Correct | 770 ms | 36588 KB | 200000 token(s): yes count is 161254, no count is 38746 |
| 3 | Correct | 265 ms | 33108 KB | 200000 token(s): yes count is 117455, no count is 82545 |
| 4 | Correct | 1137 ms | 62136 KB | 200000 token(s): yes count is 182118, no count is 17882 |
| 5 | Correct | 598 ms | 42952 KB | 200000 token(s): yes count is 167565, no count is 32435 |
| 6 | Correct | 263 ms | 33004 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 7 | Correct | 286 ms | 33096 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 8 | Correct | 258 ms | 32704 KB | 200000 token(s): yes count is 122100, no count is 77900 |
| 9 | Correct | 827 ms | 42412 KB | 200000 token(s): yes count is 139670, no count is 60330 |
| 10 | Correct | 959 ms | 42972 KB | 200000 token(s): yes count is 165806, no count is 34194 |
| 11 | Correct | 1088 ms | 51796 KB | 200000 token(s): yes count is 175646, no count is 24354 |
| 12 | Correct | 223 ms | 32688 KB | 200000 token(s): yes count is 134695, no count is 65305 |
| 13 | Correct | 215 ms | 32808 KB | 200000 token(s): yes count is 126733, no count is 73267 |
| 14 | Correct | 523 ms | 33508 KB | 200000 token(s): yes count is 155290, no count is 44710 |
| 15 | Correct | 235 ms | 32616 KB | 200000 token(s): yes count is 129674, no count is 70326 |