oj.uz

답안 #1014954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014954 2024-07-05T19:21:48 Z vjudge1 Queue (CEOI06_queue) C++17
64 / 100
 1000 ms 23240 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);
        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 = 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;
    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
64.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1090 ms 348 KB Time limit exceeded
3 Execution timed out 1052 ms 348 KB Time limit exceeded
4 Partially correct 2 ms 600 KB Partially correct
5 Correct 20 ms 4944 KB Output is correct
6 Correct 34 ms 8136 KB Output is correct
7 Correct 49 ms 6220 KB Output is correct
8 Correct 37 ms 7132 KB Output is correct
9 Partially correct 50 ms 8776 KB Partially correct
10 Partially correct 53 ms 9288 KB Partially correct
11 Correct 121 ms 13904 KB Output is correct
12 Correct 120 ms 10580 KB Output is correct
13 Correct 133 ms 14420 KB Output is correct
14 Partially correct 147 ms 14420 KB Partially correct
15 Correct 134 ms 14672 KB Output is correct
16 Correct 129 ms 14996 KB Output is correct
17 Execution timed out 1082 ms 1628 KB Time limit exceeded
18 Execution timed out 1058 ms 2284 KB Time limit exceeded
19 Execution timed out 1034 ms 3024 KB Time limit exceeded
20 Execution timed out 1045 ms 4296 KB Time limit exceeded
21 Correct 108 ms 14636 KB Output is correct
22 Correct 143 ms 17996 KB Output is correct
23 Correct 209 ms 23240 KB Output is correct
24 Correct 187 ms 22856 KB Output is correct
25 Incorrect 154 ms 16380 KB Output isn't correct