oj.uz

Submission #1014967

# Submission time Handle Problem Language Result Execution time Memory
1014967 2024-07-05T19:54:09 Z Rifal Queue (CEOI06_queue) C++14
0 / 100
 1000 ms 14280 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;
       // int pre1 = fin2(a), pre2 = fin2(b);
       // int nex1 = fin1(a);
        //cout << a << ' ' << pre1 << ' ' << nex1 << 'o' << endl;
        //cout << b << ' ' << pre2 << 'l' <<  endl;
        pre[fin1(a)] = fin2(a);
        nex[fin2(a)] = fin1(a);
        nex[fin2(b)] = a;
        pre[b] = a;
        nex[a] = b;
        pre[a] = fin2(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;
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 348 KB Time limit exceeded
2 Execution timed out 1054 ms 348 KB Time limit exceeded
3 Execution timed out 1070 ms 348 KB Time limit exceeded
4 Execution timed out 1025 ms 600 KB Time limit exceeded
5 Execution timed out 1067 ms 3404 KB Time limit exceeded
6 Execution timed out 1075 ms 5068 KB Time limit exceeded
7 Execution timed out 1068 ms 4436 KB Time limit exceeded
8 Execution timed out 1066 ms 4524 KB Time limit exceeded
9 Execution timed out 1071 ms 5712 KB Time limit exceeded
10 Execution timed out 1037 ms 5960 KB Time limit exceeded
11 Execution timed out 1014 ms 8272 KB Time limit exceeded
12 Execution timed out 1055 ms 6740 KB Time limit exceeded
13 Execution timed out 1050 ms 8868 KB Time limit exceeded
14 Execution timed out 1070 ms 8788 KB Time limit exceeded
15 Execution timed out 1049 ms 8792 KB Time limit exceeded
16 Execution timed out 1051 ms 9300 KB Time limit exceeded
17 Execution timed out 1004 ms 1624 KB Time limit exceeded
18 Execution timed out 1071 ms 2292 KB Time limit exceeded
19 Execution timed out 1034 ms 3020 KB Time limit exceeded
20 Execution timed out 1070 ms 4132 KB Time limit exceeded
21 Execution timed out 1020 ms 8912 KB Time limit exceeded
22 Execution timed out 1075 ms 11084 KB Time limit exceeded
23 Execution timed out 1042 ms 14280 KB Time limit exceeded
24 Execution timed out 1059 ms 14060 KB Time limit exceeded
25 Execution timed out 1037 ms 11080 KB Time limit exceeded