| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1014972 |
2024-07-05T20:15:52 Z |
vjudge1 |
Queue (CEOI06_queue) |
C++17 |
|
200 ms |
23128 KB |
#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
map<int, int> nex, pre, pos;
int fin1(int x)
{
if (nex.count(x) == 0)
return x + 1;
else
return nex[x];
}
int fin2(int x)
{
if (pre.count(x) == 0)
return x - 1;
else
return pre[x];
}
int main()
{
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
if(a == b) continue;
int pre1 = fin2(a), pre2 = fin2(b);
int nex1 = fin1(a);
// cout << a << ' ' << pre1 << ' ' << nex1 << 'o' << endl;
// cout << b << ' ' << pre2 << 'l' << endl;
pre[nex1] = pre1;
nex[pre1] = nex1;
nex[fin2(b)] = a;
pre[a] = fin2(b);
pre[b] = a;
nex[a] = b;
}
// cout << pre[7] << ' ' << nex[7] << ' ' << pre[8] << ' ' << nex[8] << ' ' << pre[6] << ' ' << nex[6] << 'o' << endl;
int q;
cin >> q;
vector<pair<int, int>> v, vv;
set<int> st;
pair<int, int> p[q];
for (int i = 0; i < q; i++)
{
char c;
int x;
cin >> c >> x;
p[i].fi = x;
if (c == 'L')
{
v.push_back({x, i});
p[i].se = 0;
}
else
{
vv.push_back({x, i});
st.insert(x);
p[i].se = 1;
}
}
int ans[q] = {};
sort(v.begin(), v.end());
int now = 0, indx = 0, x = 0;
while (nex.upper_bound(x) != nex.end() || nex[x] != 0)
{
if(nex[x] == 0)
{
// cout << "aa" << endl;
int y = (*nex.upper_bound(x)).first;
int indx2 = indx + (y - x);
while (now < v.size() && v[now].fi <= indx2)
{
ans[v[now].se] = x + (v[now].fi - indx);
now++;
}
auto cur = st.upper_bound(x);
while (cur != st.end() && *cur <= y)
{
pos[*cur] = indx + (*cur - x);
++cur;
}
x = y;
indx = indx2;
}
else
{
// cout << "bb" << endl;
x = nex[x];
indx++;
pos[x] = indx;
if (now < v.size() && indx == v[now].fi)
{
ans[v[now].se] = x;
now++;
}
}
}
for (int i = 0; i < vv.size(); i++)
{
ans[vv[i].se] = pos[vv[i].fi];
}
for (int i = 0; i < q; i++)
{
if (ans[i] == 0)
{
if (p[i].se == 0)
{
cout << x + (p[i].fi - indx) << endl;;
}
else
{
cout << indx + (p[i].fi - x) << endl;
}
}
else
{
cout << ans[i] << endl;
}
}
// cout << endl;o
return 0;
}
Compilation message
queue.cpp: In function 'int main()':
queue.cpp:45:29: warning: unused variable 'pre2' [-Wunused-variable]
45 | int pre1 = fin2(a), pre2 = fin2(b);
| ^~~~
queue.cpp:92:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | while (now < v.size() && v[now].fi <= indx2)
| ~~~~^~~~~~~~~~
queue.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | if (now < v.size() && indx == v[now].fi)
| ~~~~^~~~~~~~~~
queue.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < vv.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
504 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Partially correct |
2 ms |
604 KB |
Partially correct |
| 5 |
Correct |
20 ms |
4884 KB |
Output is correct |
| 6 |
Correct |
39 ms |
8136 KB |
Output is correct |
| 7 |
Correct |
32 ms |
6228 KB |
Output is correct |
| 8 |
Correct |
37 ms |
6876 KB |
Output is correct |
| 9 |
Partially correct |
50 ms |
8780 KB |
Partially correct |
| 10 |
Partially correct |
57 ms |
9288 KB |
Partially correct |
| 11 |
Correct |
139 ms |
13944 KB |
Output is correct |
| 12 |
Correct |
127 ms |
10580 KB |
Output is correct |
| 13 |
Correct |
141 ms |
14416 KB |
Output is correct |
| 14 |
Partially correct |
139 ms |
14420 KB |
Partially correct |
| 15 |
Correct |
128 ms |
14524 KB |
Output is correct |
| 16 |
Correct |
149 ms |
14928 KB |
Output is correct |
| 17 |
Correct |
16 ms |
1748 KB |
Output is correct |
| 18 |
Correct |
32 ms |
2744 KB |
Output is correct |
| 19 |
Partially correct |
49 ms |
3788 KB |
Partially correct |
| 20 |
Correct |
97 ms |
5324 KB |
Output is correct |
| 21 |
Correct |
111 ms |
14836 KB |
Output is correct |
| 22 |
Correct |
136 ms |
18208 KB |
Output is correct |
| 23 |
Correct |
187 ms |
23128 KB |
Output is correct |
| 24 |
Correct |
200 ms |
22796 KB |
Output is correct |
| 25 |
Partially correct |
160 ms |
16400 KB |
Partially correct |
