oj.uz

답안 #1014957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014957 2024-07-05T19:23:06 Z Rifal Queue (CEOI06_queue) C++14
64 / 100
 1000 ms 21704 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 1095 ms 348 KB Time limit exceeded
3 Execution timed out 1046 ms 344 KB Time limit exceeded
4 Partially correct 3 ms 600 KB Partially correct
5 Correct 21 ms 4432 KB Output is correct
6 Correct 41 ms 7628 KB Output is correct
7 Correct 34 ms 5456 KB Output is correct
8 Correct 41 ms 6112 KB Output is correct
9 Partially correct 51 ms 8068 KB Partially correct
10 Partially correct 59 ms 8476 KB Partially correct
11 Correct 131 ms 12876 KB Output is correct
12 Correct 116 ms 9800 KB Output is correct
13 Correct 157 ms 13648 KB Output is correct
14 Partially correct 137 ms 13512 KB Partially correct
15 Correct 153 ms 13392 KB Output is correct
16 Correct 145 ms 13788 KB Output is correct
17 Execution timed out 1064 ms 992 KB Time limit exceeded
18 Execution timed out 1049 ms 1512 KB Time limit exceeded
19 Execution timed out 1066 ms 2000 KB Time limit exceeded
20 Execution timed out 1076 ms 2824 KB Time limit exceeded
21 Correct 94 ms 13928 KB Output is correct
22 Correct 145 ms 16972 KB Output is correct
23 Correct 196 ms 21704 KB Output is correct
24 Correct 198 ms 21320 KB Output is correct
25 Incorrect 143 ms 14928 KB Output isn't correct