Submission #658357

#	Time	Username	Problem	Language	Result	Execution time	Memory
658357		Dec0Dedd	Queue (CEOI06_queue)	C++14	100 / 100	245 ms	21556 KiB

queue

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

map<int, int> bf, af, s[2];
map<int, pii> pos;

const int N = 5e4+1;
const int INF = 1e9+7;

int prv(int x) {
   if (bf.find(x) != bf.end()) return bf[x];
   return x+1;
}

int nxt(int x) {
   if (af.find(x) != af.end()) return af[x];
   return x-1;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   
   int n, x=1; cin>>n;
   for (int i=1; i<=n; ++i) {
      int a, b; cin>>a>>b;
      int afr=nxt(a), abk=prv(a), bfr=nxt(b);
      if (a == b || abk == b) continue;
      af[abk]=afr, bf[afr]=abk;
      af[a]=bfr, bf[bfr]=a;
      af[b]=a, bf[a]=b;
      if (x == a) x=abk;
      if (x == b) x=a;
   } bf[INF]=INF;

   for (int i=x, j=1; i<INF;) {
      auto it=bf.lower_bound(i);
      int e=(*it).first; j+=e-i;
      s[0][e]=j, s[1][j]=e;
      i=(*it).second; ++j;
   }

   int q; cin>>q;
   while (q--) {
      char c; cin>>c;
      int a; cin>>a;

      auto p=s[c == 'L'].lower_bound(a);
      cout<<(p->second-p->first+a)<<"\n";
   }
}

• Subtask 1: 100 / 100