Submission #135808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135808	2019-07-24T11:42:30 Z	model_code	Queue (CEOI06_queue)	C++14	100 / 100	412 ms	13176 KB

queue

#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

map<int,int> map_next, map_prev;
multimap<int,int> L_queries, P_queries;
typedef multimap<int,int>::iterator mapiterator;

int next( int x ) {
   if( map_next.count( x ) ) return map_next[x];
   return x+1;
}
int prev( int x ) {
   if( map_prev.count( x ) ) return map_prev[x];
   return x-1;
}

int n, q;
const int inf = 2000000000;

void input_list() {
   scanf( "%d", &n );
   for( int i = 0; i < n; ++i ) {
      int a, b;
      scanf( "%d%d", &a, &b );
      map_next[prev(a)] = next(a);
      map_prev[next(a)] = prev(a);

      int c = prev(b);
      map_next[c] = a;
      map_prev[a] = c;
      map_next[a] = b;
      map_prev[b] = a;
   }
   map_next[inf] = inf+1;
}

void input_queries() {
   scanf( "%d", &q );
   for( int i = 0; i < q; ++i ) {
      char type;
      int x;
      scanf( " %c %d", &type, &x );
      if( type == 'L' ) L_queries.insert( pair<int,int>(x, i) );
      if( type == 'P' ) P_queries.insert( pair<int,int>(x, i) );
   }
   L_queries.insert( pair<int,int>(inf, q) );
   P_queries.insert( pair<int,int>(inf, q) );
}

int main( void ) {

   input_list();
   input_queries();

   vector< int > ret( q+1 );
   int label = 0, position = 0;

   while( label < inf ) {
      int a = map_next.lower_bound( label )->first - label;
      int b = L_queries.lower_bound( position )->first - position;
      int c = P_queries.lower_bound( label )->first - label;

      int mini = std::min({a, b, c});

      label += mini;
      position += mini;

      if( mini == b ) {
         pair<mapiterator,mapiterator> eq = L_queries.equal_range( position );
         for( mapiterator it = eq.first; it != eq.second; ++it )
            ret[it->second] = label;
      }
      if( mini == c ) {
         pair<mapiterator,mapiterator> eq = P_queries.equal_range( label );
         for( mapiterator it = eq.first; it != eq.second; ++it )
            ret[it->second] = position;
      }

      label = next(label);
      ++position;
   }

   for( int i = 0; i < q; ++i )
      printf( "%d\n", ret[i] );

   return 0;
}

Compilation message

queue.cpp: In function 'void input_list()':
queue.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d", &n );
    ~~~~~^~~~~~~~~~~~
queue.cpp:28:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( "%d%d", &a, &b );
       ~~~~~^~~~~~~~~~~~~~~~~~
queue.cpp: In function 'void input_queries()':
queue.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d", &q );
    ~~~~~^~~~~~~~~~~~
queue.cpp:46:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( " %c %d", &type, &x );
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	65 ms	3576 KB	Output is correct
6	Correct	70 ms	4088 KB	Output is correct
7	Correct	97 ms	4728 KB	Output is correct
8	Correct	102 ms	5684 KB	Output is correct
9	Correct	125 ms	5892 KB	Output is correct
10	Correct	122 ms	6184 KB	Output is correct
11	Correct	252 ms	7544 KB	Output is correct
12	Correct	228 ms	6268 KB	Output is correct
13	Correct	283 ms	7744 KB	Output is correct
14	Correct	263 ms	7928 KB	Output is correct
15	Correct	281 ms	8084 KB	Output is correct
16	Correct	264 ms	8164 KB	Output is correct
17	Correct	42 ms	1528 KB	Output is correct
18	Correct	74 ms	2552 KB	Output is correct
19	Correct	110 ms	3436 KB	Output is correct
20	Correct	189 ms	4272 KB	Output is correct
21	Correct	205 ms	8828 KB	Output is correct
22	Correct	308 ms	10948 KB	Output is correct
23	Correct	412 ms	13176 KB	Output is correct
24	Correct	386 ms	12996 KB	Output is correct
25	Correct	332 ms	10872 KB	Output is correct