Submission #1010889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010889	2024-06-29T13:40:11 Z	vjudge1	Queue (CEOI06_queue)	C++17	50 / 100	1000 ms	21708 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;
    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;
    return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:87: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]
   87 |             while (now < v.size() && v[now].fi <= indx2)
      |                    ~~~~^~~~~~~~~~
queue.cpp:107: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]
  107 |             if (now < v.size() && indx == v[now].fi)
      |                 ~~~~^~~~~~~~~~
queue.cpp:114: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]
  114 |     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	344 KB	Partially correct
2	Execution timed out	1020 ms	344 KB	Time limit exceeded
3	Execution timed out	1040 ms	344 KB	Time limit exceeded
4	Partially correct	2 ms	600 KB	Partially correct
5	Incorrect	19 ms	4388 KB	Output isn't correct
6	Correct	38 ms	7624 KB	Output is correct
7	Incorrect	30 ms	5456 KB	Output isn't correct
8	Partially correct	39 ms	6104 KB	Partially correct
9	Partially correct	50 ms	8012 KB	Partially correct
10	Partially correct	53 ms	8520 KB	Partially correct
11	Correct	146 ms	12892 KB	Output is correct
12	Correct	106 ms	9868 KB	Output is correct
13	Correct	136 ms	13508 KB	Output is correct
14	Partially correct	145 ms	13396 KB	Partially correct
15	Correct	136 ms	13544 KB	Output is correct
16	Correct	134 ms	13908 KB	Output is correct
17	Execution timed out	1064 ms	992 KB	Time limit exceeded
18	Execution timed out	1074 ms	1492 KB	Time limit exceeded
19	Execution timed out	1071 ms	2008 KB	Time limit exceeded
20	Execution timed out	1079 ms	2776 KB	Time limit exceeded
21	Correct	100 ms	13776 KB	Output is correct
22	Partially correct	135 ms	16964 KB	Partially correct
23	Correct	189 ms	21708 KB	Output is correct
24	Correct	205 ms	21324 KB	Output is correct
25	Incorrect	152 ms	14920 KB	Output isn't correct