Submission #1010893

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010893	2024-06-29T13:49:31 Z	vjudge1	Queue (CEOI06_queue)	C++17	50 / 100	333 ms	21692 KB

queue

#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;
        int pre1 = fin2(a), pre2 = fin2(b);
        int nex1 = fin1(a);
        pre[nex1] = pre1;
        nex[pre1] = nex1;
        nex[pre2] = a;
        pre[b] = a;
        nex[a] = b;
        pre[a] = pre2;
    }
    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 = c;
        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;
    int cnt = 0; 
    while (nex.upper_bound(x) != nex.end() || nex[x] != 0)
    {
        cnt++;
        if(cnt == 1000000) {
            break;
        }
        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;
        }
    }
    return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:91: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]
   91 |             while (now < v.size() && v[now].fi <= indx2)
      |                    ~~~~^~~~~~~~~~
queue.cpp:111: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]
  111 |             if (now < v.size() && indx == v[now].fi)
      |                 ~~~~^~~~~~~~~~
queue.cpp:118: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]
  118 |     for (int i = 0; i < vv.size(); i++)
      |                     ~~^~~~~~~~~~~

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	348 KB	Partially correct
2	Incorrect	11 ms	348 KB	Output isn't correct
3	Incorrect	18 ms	348 KB	Output isn't correct
4	Partially correct	2 ms	604 KB	Partially correct
5	Incorrect	23 ms	4360 KB	Output isn't correct
6	Correct	40 ms	7628 KB	Output is correct
7	Incorrect	39 ms	5448 KB	Output isn't correct
8	Partially correct	47 ms	6368 KB	Partially correct
9	Partially correct	57 ms	8008 KB	Partially correct
10	Partially correct	56 ms	8624 KB	Partially correct
11	Correct	143 ms	12884 KB	Output is correct
12	Correct	119 ms	9752 KB	Output is correct
13	Correct	170 ms	13344 KB	Output is correct
14	Partially correct	147 ms	13396 KB	Partially correct
15	Correct	140 ms	13396 KB	Output is correct
16	Correct	146 ms	13968 KB	Output is correct
17	Incorrect	33 ms	1000 KB	Output isn't correct
18	Incorrect	91 ms	1804 KB	Output isn't correct
19	Incorrect	232 ms	2508 KB	Output isn't correct
20	Incorrect	333 ms	3492 KB	Output isn't correct
21	Correct	104 ms	13720 KB	Output is correct
22	Partially correct	158 ms	16972 KB	Partially correct
23	Correct	220 ms	21692 KB	Output is correct
24	Correct	214 ms	21320 KB	Output is correct
25	Incorrect	172 ms	14948 KB	Output isn't correct