Submission #1225254

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

struct seg {
  vector<int> d; int n;
  seg(){}
  seg(int mx) {
    n = 1; while (n < mx) n <<= 1;
    d = vector<int>(n<<1);
  }
  void upd(int i) {
    int l = i<<1, r = i<<1|1;
    int x = min(d[l], d[r]);
    d[i] += x;
    d[l] -= x; d[r] -= x;
  }
  void add(int l, int x) {
    l += n; int r = n<<1;
    int sl = l;
    while (l<r) {
      if (l&1) d[l++] += x;
      l >>= 1; r >>= 1;
    }
    while (!(sl&1)) sl >>= 1;
    sl >>= 1;
    while (sl) {
      upd(sl);
      sl >>= 1;
    }
  }
  int get(int l, int r) { return get(l,r,1,0,n);}
  int get(int a, int b, int i, int l, int r) {
    if (a <= l && r <= b) return d[i];
    int c = (l+r)>>1;
    int res = INF;
    if (a < c) mins(res, get(a,b,i<<1,l,c));
    if (c < b) mins(res, get(a,b,i<<1|1,c,r));
    res += d[i];
    return res;
  }
  int pos(int l, int r, int x) { return pos(l,r,x,1,0,n);}
  int pos(int a, int b, int x, int i, int l, int r) {
    x -= d[i];
    if (a <= l && r <= b) {
      if (x < 0) return -1;
      while (i < n) {
        i <<= 1;
        if (x-d[i] < 0) i |= 1;
        x -= d[i];
      }
      return i-n;
    }
    int c = (l+r)>>1;
    if (a < c) {
      int p = pos(a,b,x,i<<1,l,c);
      if (p != -1) return p;
    }
    if (c < b) {
      int p = pos(a,b,x,i<<1|1,c,r);
      if (p != -1) return p;
    }
    return -1;
  }
};

// coordinate compression
struct X {
  typedef int T;
  vector<T> d;
  void add(T x) { d.pb(x);}
  void init() {
    sort(rng(d));
    // d.erase(unique(rng(d)), d.end());
  }
  int size() const { return sz(d);}
  int operator[](int i) const { return d[i];}
  int operator()(T x) const { return lower_bound(rng(d),x)-d.begin();}
};
//


int n, m;
vi a, b;
X xs;
vi dp;
vi mx;

bool calc() {
  dp = vi(m,-INF);
  multiset<int> s;
  vvi as(m);
  rep(i,n) as[a[i]].pb(i);
  bool end = false;
  int ei = -1;
  int cnt = 0;
  rep(i,m) {
    for (int j : as[i]) {
      s.insert(b[j]);
    }
    while (1) {
      auto it = s.begin();
      if (it == s.end()) break;
      if (*it == i) {
        s.erase(it);
        s.insert(INF);
      } else break;
    }
    if (!sz(s)) {
      if (end) return false;
      end = true;
      ei = i;
    } else {
      auto it = s.end(); --it;
      if (*it == INF) cnt++;
      if (!end) mx.pb(*it);
      s.erase(it);
    }
  }
  assert(end);
  dp[ei] = cnt;
  return true;
}

const int D = 350;
void calc2() {
  int w = sz(mx);
  vvi es(m);
  rep(i,w) if (mx[i] != INF) es[mx[i]].pb(i);
  vvi bs(m);
  rep(i,n) bs[b[i]].pb(i);
  X xb;
  int sum = 0;
  rep(i,m) {
    sum += sz(bs[i])+1;
    if (i == m-1 || sum > D) {
      sum = 0;
      xb.add(i);
    }
  }
  vi id;
  rep(i,w) if (mx[i] < m) id.pb(i);
  sort(rng(id), [&](int i, int j) {
    int bi = xb(mx[i]), bj = xb(mx[j]);
    if (bi == bj) return bool((i<j)^(bi&1));
    return bi<bj;
  });

  seg t(m);
  rep(i,m) t.add(i,-1);
  rep(i,n) t.add(a[i],1);
  rep(i,n) t.add(b[i],1);

  vi nx(w), ad(w);
  int l = 0, r = 0;
  for (int nl : id) {
    int nr = mx[nl];
    while (r<nr) {
      for (int i : bs[r]) {
        t.add(a[i],-1);
      }
      ++r;
    }
    while (nl<l) {
      --l;
      if (mx[l] < m) t.add(mx[l],1);
    }
    while (r>nr) {
      --r;
      for (int i : bs[r]) {
        t.add(a[i],1);
      }
    }
    while (nl>l) {
      if (mx[l] < m) t.add(mx[l],-1);
      ++l;
    }
    {
      int i = nl;
      int sx = t.get(nl,nl+1);
      int p = t.pos(nl,nr,sx-1);
      if (p == -1) {
        nx[i] = nr; ad[i] = 1;
      } else {
        nx[i] = p;
      }
    }
  }
  drep(i,w) {
    if (mx[i] == INF) dp[i] = dp[i+1];
    else dp[i] = dp[nx[i]]+ad[i];
  }
}

int main() {
  scanf("%d",&n);
  m = n+1;
  a = b = vi(n);
  rep(i,n) scanf("%d%d",&a[i],&b[i]);
  rep(j,m) {
    int c;
    scanf("%d",&c);
    xs.add(c);
  }
  int q;
  scanf("%d",&q);
  xs.init();
  int del = 0;
  rep(i,n) {
    a[i] = xs(a[i]);
    b[i] = xs(b[i]);
    swap(a[i],b[i]); // a:back
    mins(a[i],b[i]);
    if (a[i] > n) {
      rep(j,q) puts("-1");
      return 0;
    }
    if (b[i] > n) {
      b[i] = a[i];
      ++del;
    }
  }
  if (!calc()) {
    rep(j,q) puts("-1");
    return 0;
  }
  calc2();
  rep(qi,q) {
    int nb,na;
    scanf("%d%d",&nb,&na);
    na = xs(na);
    nb = xs(nb);
    mins(na,nb);
    if (na > n) {
      puts("-1");
      continue;
    }
    int ans = dp[na];
    if (nb <= n) maxs(ans,dp[nb]+1);
    if (ans < 0) ans = -1;
    else ans -= del;
    printf("%d\n",ans);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:259:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:262:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   rep(i,n) scanf("%d%d",&a[i],&b[i]);
                                     ^
./Main.cpp:265:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&c);
                   ^
./Main.cpp:269:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
                 ^
./Main.cpp:293:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&nb,&na);
                          ^

Judge Result