Submission #856856

---

Source Code Expand

#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

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