Submission #856856


Source Code Expand

Copy
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<functional>
using namespace std;
const int MAX = 100000 + 10;

int rec[MAX];
int tar[MAX];
bool sta[MAX];

struct myType{
  int x, y, z;
  myType(int _x, int _y, int _z):x(_x),y(_y),z(_z){}
  bool operator<(const myType &a) const{
    if(x==a.x){
      return y < a.y;
    }
    return x < a.x;
  }
};
multimap< myType, int> my_map;
vector< pair<int, int> > ans;

int go(int x, int y){
  int ret = 0;
  while(x < y){
    x = tar[x];
    ret ++;
  }
  return ret;
}

int main(){
  int n, l;
  scanf("%d", &n);
  
  for(int i = 0 ; i < n ; i++){
    scanf("%d", &rec[i]);
  }

  scanf("%d", &l);
  int ls = 0;
  for(int i = 1 ; i < n ; i++){
    while (rec[i] - rec[ls] > l) {
      tar[ls] = i-1;
      ls++;
    }
  }
  for(int i = ls ; i < n ; i++){
    tar[i] = n;
  }
  
  int q;
  scanf("%d", &q);
  for(int i = 0 ; i < q ; i++){
    int p, s;
    scanf("%d %d", &p, &s);
    p--, s--;
    if(p > s) swap(p, s);
    sta[p] = true;
    my_map.insert( make_pair (myType(p,s,i), 0) );
  }

  while (my_map.size() > 0) {
    multimap<myType, int> :: iterator itr = my_map.begin(), titr;
    myType tmp = itr -> first;
    int start = itr->first.x;
    int value = itr -> second, add = 0;
    titr = itr;
    itr++;
    my_map.erase(titr);
    sta[tmp.x] = false;
    while (sta[tmp.x] == false && tmp.x < tmp.y) {
      add++;
      tmp.x = tar[tmp.x];
    }
    if (sta[tmp.x]) {
      my_map.insert( make_pair(tmp, value+add) );
    } else {
      ans.push_back(make_pair(tmp.z, value+add));
    }
    if(start != tmp.x){
      while(itr != my_map.end() && itr->first.x == start){
        myType tpack = itr->first;
        int tvalue = itr->second;
        tpack.x = tmp.x;
        if(tpack.x >= tpack.y){
          ans.push_back( make_pair(tpack.z, tvalue+add));
        }else{
          my_map.insert( make_pair(tpack, tvalue+add) );
          sta[tpack.x] = true;
        }
        titr = itr;
        itr++;
        my_map.erase(titr);
      }
    }
  }
  
  sort(ans.begin(), ans.end());
  for(int i = 0 ; i < (int)ans.size() ; i++){
    printf("%d\n", ans[i].second);
  }

  return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User bigelephant29
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2281 Byte
Status TLE
Exec Time 3157 ms
Memory 8572 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:40:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &rec[i]);
                         ^
./Main.cpp:43:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &l);
                  ^
./Main.cpp:56:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
                  ^
./Main.cpp:59:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &p, &s);
                           ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 500
Status
AC × 1
AC × 14
AC × 17
TLE × 10
Set Name Test Cases
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 11 ms 384 KB
subtask1_04.txt AC 69 ms 384 KB
subtask1_05.txt AC 6 ms 384 KB
subtask1_06.txt AC 20 ms 256 KB
subtask1_07.txt AC 5 ms 256 KB
subtask1_08.txt AC 5 ms 384 KB
subtask1_09.txt AC 20 ms 384 KB
subtask1_10.txt AC 50 ms 384 KB
subtask1_11.txt AC 52 ms 384 KB
subtask1_12.txt AC 49 ms 384 KB
subtask1_13.txt AC 44 ms 384 KB
subtask2_01.txt TLE 3157 ms 7424 KB
subtask2_02.txt TLE 3157 ms 7296 KB
subtask2_03.txt TLE 3157 ms 7552 KB
subtask2_04.txt AC 101 ms 5628 KB
subtask2_05.txt TLE 3156 ms 4992 KB
subtask2_06.txt AC 159 ms 8572 KB
subtask2_07.txt TLE 3157 ms 7424 KB
subtask2_08.txt TLE 3157 ms 7296 KB
subtask2_09.txt TLE 3154 ms 7296 KB
subtask2_10.txt TLE 3154 ms 7296 KB
subtask2_11.txt TLE 3154 ms 7296 KB
subtask2_12.txt TLE 3154 ms 7296 KB
subtask2_13.txt AC 216 ms 8572 KB