oj.uz

답안 #1010889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010889 2024-06-29T13:40:11 Z vjudge1 Queue (CEOI06_queue) C++17
50 / 100
 1000 ms 21708 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 = 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

# 결과 실행 시간 메모리 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