oj.uz

답안 #1014972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014972 2024-07-05T20:15:52 Z vjudge1 Queue (CEOI06_queue) C++17
88 / 100
 200 ms 23128 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;
        if(a == b) continue;
        int pre1 = fin2(a), pre2 = fin2(b);
        int nex1 = fin1(a);
       // cout << a << ' ' << pre1 << ' ' << nex1 << 'o' << endl;
       // cout << b << ' ' << pre2 << 'l' <<  endl;
        pre[nex1] = pre1;
        nex[pre1] = nex1;
        nex[fin2(b)] = a;
        pre[a] = fin2(b);
        pre[b] = a;
        nex[a] = 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;
        }
    }
//    cout << endl;o
    return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:45:29: warning: unused variable 'pre2' [-Wunused-variable]
   45 |         int pre1 = fin2(a), pre2 = fin2(b);
      |                             ^~~~
queue.cpp:92: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]
   92 |             while (now < v.size() && v[now].fi <= indx2)
      |                    ~~~~^~~~~~~~~~
queue.cpp:112: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]
  112 |             if (now < v.size() && indx == v[now].fi)
      |                 ~~~~^~~~~~~~~~
queue.cpp:119: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]
  119 |     for (int i = 0; i < vv.size(); i++)
      |                     ~~^~~~~~~~~~~

Subtask #1
88.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Partially correct 2 ms 604 KB Partially correct
5 Correct 20 ms 4884 KB Output is correct
6 Correct 39 ms 8136 KB Output is correct
7 Correct 32 ms 6228 KB Output is correct
8 Correct 37 ms 6876 KB Output is correct
9 Partially correct 50 ms 8780 KB Partially correct
10 Partially correct 57 ms 9288 KB Partially correct
11 Correct 139 ms 13944 KB Output is correct
12 Correct 127 ms 10580 KB Output is correct
13 Correct 141 ms 14416 KB Output is correct
14 Partially correct 139 ms 14420 KB Partially correct
15 Correct 128 ms 14524 KB Output is correct
16 Correct 149 ms 14928 KB Output is correct
17 Correct 16 ms 1748 KB Output is correct
18 Correct 32 ms 2744 KB Output is correct
19 Partially correct 49 ms 3788 KB Partially correct
20 Correct 97 ms 5324 KB Output is correct
21 Correct 111 ms 14836 KB Output is correct
22 Correct 136 ms 18208 KB Output is correct
23 Correct 187 ms 23128 KB Output is correct
24 Correct 200 ms 22796 KB Output is correct
25 Partially correct 160 ms 16400 KB Partially correct