AtCoder Grand Contest 013

Submission #1225254

Source codeソースコード

#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

Task問題 F - Two Faced Cards
User nameユーザ名 ຣസںƙᘓ
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 0
Source lengthソースコード長 6993 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 0 / 2000 sample_01.txt,sample_02.txt,sample_03.txt,sample_01.txt,sample_02.txt,sample_03.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt,subtask_1_42.txt,subtask_1_43.txt,subtask_1_44.txt,subtask_1_45.txt,subtask_1_46.txt,subtask_1_47.txt,subtask_1_48.txt,subtask_1_49.txt,subtask_1_50.txt,subtask_1_51.txt,subtask_1_52.txt,subtask_1_53.txt,subtask_1_54.txt,subtask_1_55.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 103 ms 6512 KB
subtask_1_02.txt AC 158 ms 8228 KB
subtask_1_03.txt AC 53 ms 3376 KB
subtask_1_04.txt AC 180 ms 10960 KB
subtask_1_05.txt AC 57 ms 2712 KB
subtask_1_06.txt AC 475 ms 8228 KB
subtask_1_07.txt AC 72 ms 7288 KB
subtask_1_08.txt TLE
subtask_1_09.txt AC 144 ms 9180 KB
subtask_1_10.txt AC 91 ms 5840 KB
subtask_1_11.txt AC 37 ms 3836 KB
subtask_1_12.txt AC 1058 ms 8144 KB
subtask_1_13.txt AC 100 ms 5604 KB
subtask_1_14.txt AC 93 ms 4648 KB
subtask_1_15.txt AC 53 ms 5624 KB
subtask_1_16.txt AC 218 ms 2540 KB
subtask_1_17.txt AC 204 ms 11684 KB
subtask_1_18.txt AC 100 ms 4572 KB
subtask_1_19.txt AC 44 ms 4476 KB
subtask_1_20.txt TLE
subtask_1_21.txt AC 219 ms 10704 KB
subtask_1_22.txt AC 319 ms 15440 KB
subtask_1_23.txt AC 227 ms 10704 KB
subtask_1_24.txt AC 323 ms 15436 KB
subtask_1_25.txt AC 213 ms 11888 KB
subtask_1_26.txt AC 1606 ms 12624 KB
subtask_1_27.txt AC 76 ms 7544 KB
subtask_1_28.txt TLE
subtask_1_29.txt AC 211 ms 11888 KB
subtask_1_30.txt AC 1576 ms 12496 KB
subtask_1_31.txt AC 76 ms 7544 KB
subtask_1_32.txt TLE
subtask_1_33.txt AC 211 ms 11888 KB
subtask_1_34.txt AC 1033 ms 11984 KB
subtask_1_35.txt AC 76 ms 7416 KB
subtask_1_36.txt TLE
subtask_1_37.txt AC 211 ms 11888 KB
subtask_1_38.txt AC 995 ms 11984 KB
subtask_1_39.txt AC 77 ms 7672 KB
subtask_1_40.txt TLE
subtask_1_41.txt AC 197 ms 9448 KB
subtask_1_42.txt AC 193 ms 9936 KB
subtask_1_43.txt AC 190 ms 9552 KB
subtask_1_44.txt AC 420 ms 8912 KB
subtask_1_45.txt AC 63 ms 5112 KB
subtask_1_46.txt AC 183 ms 9316 KB
subtask_1_47.txt AC 164 ms 9368 KB
subtask_1_48.txt AC 172 ms 9256 KB
subtask_1_49.txt AC 574 ms 9492 KB
subtask_1_50.txt AC 55 ms 4728 KB
subtask_1_51.txt AC 1 ms 256 KB
subtask_1_52.txt AC 1 ms 256 KB
subtask_1_53.txt AC 1 ms 256 KB
subtask_1_54.txt AC 1 ms 256 KB
subtask_1_55.txt AC 1 ms 256 KB