Submission #1010893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010893		vjudge1	Queue (CEOI06_queue)	C++17	50 / 100	333 ms	21692 KiB

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 (stderr)

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 / 100