Submission #534668
Source Code Expand
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <unordered_map>
#include <iterator>
#include <functional>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}
const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;
struct handler{
typedef int val_t;
handler(){}
inline static val_t def_val(){ return 0; }
inline static val_t update(const val_t &l, const val_t &r){
return r;
}
inline static val_t merge(const val_t &l, const val_t &r){
return max(l, r);
}
};
template<class H>
struct RBST{
unsigned long xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t=(x^(x<<11));x=y;y=z;z=w; return w=(w^(w>>19))^(t^(t>>8));
}
typedef typename H::val_t val_t;
struct Node{
val_t v, sum;
Node* ch[2];
int c;
Node(const val_t &v):v(v), sum(v), c(1){ch[0]=ch[1]=0;}
};
typedef pair<Node*, Node*> PNode;
int count(Node* v){return v ? v->c : 0;}
val_t val(Node* v){return v ? v->v : H::def_val();}
val_t sum(Node* v){return v ? v->sum : H::def_val();}
Node* update(Node *v){
v->c = count(v->ch[0]) + count(v->ch[1]) + 1;
v->sum = H::merge(H::merge(sum(v->ch[0]), v->v), sum(v->ch[1]));
return v;
}
Node* merge(Node* l, Node* r){
if(!l || !r) return !l ? r : l;
if(xor128() % (count(l) + count(r)) < count(l)){
l->ch[1] = merge(l->ch[1], r);
return update(l);
}else{
r->ch[0] = merge(l, r->ch[0]);
return update(r);
}
}
PNode split(Node *v, int k){ // [0, k), [k, n)
if(!v) return PNode(0, 0);
if(k <= count(v->ch[0])){
PNode s = split(v->ch[0], k);
v->ch[0] = s.second;
return PNode(s.first, update(v));
}else{
PNode s = split(v->ch[1], k - count(v->ch[0]) - 1);
v->ch[1] = s.first;
return PNode(update(v), s.second);
}
}
Node* insert(Node *v, int k, Node *t){
if(!v || !t) return !t ? v : t;
PNode s = split(v, k);
return merge(merge(s.first, t), s.second);
}
Node* insert(Node *v, int k, const val_t &val){
return insert(v, k, new Node(val));
}
Node* erase(Node* v, int k){
PNode s = split(v, k);
PNode p = split(s.second, 1);
// delete p.first;
return merge(s.first, p.second);
}
val_t kth(Node* v, int k){
if(!v) return H::def_val();
if(k == count(v->ch[0])) return val(v);
if(k < count(v->ch[0])) return kth(v->ch[0], k);
else return kth(v->ch[1], k - count(v->ch[0]) - 1);
}
int lb(Node* v, const val_t &val){
if(!v) return 0;
if(v->v == val) return count(v->ch[0]);
if(v->v < val) return count(v->ch[0]) + 1 + lb(v->ch[1], val);
return lb(v->ch[0], val);
}
int find(Node* v, const val_t &val){
if(!v) return 0;
if(sum(v->ch[1]) >= val) return count(v->ch[0]) + 1 + find(v->ch[1], val);
if(v->v >= val) return count(v->ch[0]);
return find(v->ch[0], val);
}
val_t query(Node *v, int l, int r, int k=0){
if(!v || r <= 0 || count(v) <= l) return H::def_val();
if(l<=0 && count(v) <= r) return v->sum;
if(r <= count(v->ch[0])) return query(v->ch[0], l, r, k);
if(count(v->ch[0]) < l) return query(v->ch[1], l-count(v->ch[0])-1, r-count(v->ch[0])-1, k+count(v->ch[0])+1);
return H::merge(query(v->ch[0], l, r, k), H::merge(v->v,
query(v->ch[1], l-count(v->ch[0])-1, r-count(v->ch[0])-1, k+count(v->ch[0])+1)));
}
Node* update(Node* v, int k, const val_t &val){
if(!v || k < 0 || count(v) <= k) return v;
if(k == count(v->ch[0])) v->v = H::update(v->v, val);
else if(k < count(v->ch[0])) update(v->ch[0], k, val);
else update(v->ch[1], k-count(v->ch[0])-1, val);
return update(v);
}
Node* build(const vector<val_t> &val, int l=0, int r=-1){
if(r==-1) r = val.size();
if(r<=l) return 0;
Node *v = new Node(val[(l+r)/2]);
v->ch[0] = build(val, l, (l+r)/2);
v->ch[1] = build(val, (l+r)/2+1, r);
return update(v);
}
friend ostream& operator<<(ostream &os, Node* v){
if(!v) return os;
if(v->ch[0]) os << v->ch[0] << ", ";
os << v->v;
if(v->ch[1]) os << ", " << v->ch[1];
return os;
}
};
int T, n, m;
int main(int argc, char *argv[]){
ios::sync_with_stdio(false);
cin >> n;
vi a(n), b(n), c(n);
REP(i, n) cin >> a[i];
REP(i, n) cin >> b[i];
c = a;
sort(ALL(c));
REP(i, n) if(c[i] < b[i]){
cout << -1 << endl;
return 0;
}
RBST<handler> rbst;
auto root = rbst.build(a);
ll ans = 0;
RREP(i, n){
int ai = rbst.kth(root, i);
if(ai < b[i]){
auto res = rbst.split(root, i + 1);
int k = rbst.find(res.first, b[i]);
ans += i - k;
auto p1 = rbst.split(res.first, k);
auto p2 = rbst.split(p1.second, 1);
// cout << p1.first << endl;
// cout << p2.first << endl;
// cout << p2.second << endl;
// cout << res.second << endl;
// cout << "..." << endl;
root = rbst.merge(rbst.merge(p1.first, p2.second), rbst.merge(p2.first, res.second));
// cout << "---" << endl;
// cout << root << endl;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - ケンドー |
User |
zerokugi |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
7115 Byte |
Status |
AC |
Exec Time |
335 ms |
Memory |
6692 KB |
Judge Result
Set Name |
Small |
All |
Score / Max Score |
3 / 3 |
297 / 297 |
Status |
|
|
Set Name |
Test Cases |
Small |
00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt |
All |
00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 20_large_01.txt, 20_large_02.txt, 20_large_03.txt, 20_large_04.txt, 20_large_05.txt, 20_large_06.txt, 20_large_07.txt, 20_large_08.txt, 20_large_09.txt, 20_large_10.txt, 30_maxcase_01.txt, 31_almost_maxcase_01.txt, 31_almost_maxcase_02.txt, 31_almost_maxcase_03.txt, 31_almost_maxcase_04.txt, 31_almost_maxcase_05.txt, 40_bad_maxcase_01.txt, 40_bad_maxcase_02.txt, 40_bad_maxcase_03.txt, 40_bad_maxcase_04.txt, 40_bad_maxcase_05.txt, 41_bad_shufflecase_01.txt, 41_bad_shufflecase_02.txt, 41_bad_shufflecase_03.txt, 41_bad_shufflecase_04.txt |
Case Name |
Status |
Exec Time |
Memory |
00_small_sample_00.txt |
AC |
27 ms |
740 KB |
00_small_sample_01.txt |
AC |
25 ms |
924 KB |
00_small_sample_02.txt |
AC |
26 ms |
812 KB |
10_small_01.txt |
AC |
26 ms |
800 KB |
10_small_02.txt |
AC |
27 ms |
928 KB |
10_small_03.txt |
AC |
26 ms |
924 KB |
10_small_04.txt |
AC |
27 ms |
800 KB |
10_small_05.txt |
AC |
26 ms |
924 KB |
10_small_06.txt |
AC |
27 ms |
864 KB |
10_small_07.txt |
AC |
31 ms |
928 KB |
10_small_08.txt |
AC |
27 ms |
940 KB |
10_small_09.txt |
AC |
27 ms |
928 KB |
10_small_10.txt |
AC |
26 ms |
808 KB |
20_large_01.txt |
AC |
307 ms |
6180 KB |
20_large_02.txt |
AC |
304 ms |
6180 KB |
20_large_03.txt |
AC |
328 ms |
6432 KB |
20_large_04.txt |
AC |
335 ms |
6568 KB |
20_large_05.txt |
AC |
333 ms |
6432 KB |
20_large_06.txt |
AC |
334 ms |
6368 KB |
20_large_07.txt |
AC |
301 ms |
6056 KB |
20_large_08.txt |
AC |
321 ms |
6436 KB |
20_large_09.txt |
AC |
330 ms |
6568 KB |
20_large_10.txt |
AC |
312 ms |
6296 KB |
30_maxcase_01.txt |
AC |
260 ms |
6692 KB |
31_almost_maxcase_01.txt |
AC |
334 ms |
6564 KB |
31_almost_maxcase_02.txt |
AC |
316 ms |
6448 KB |
31_almost_maxcase_03.txt |
AC |
315 ms |
6560 KB |
31_almost_maxcase_04.txt |
AC |
303 ms |
6560 KB |
31_almost_maxcase_05.txt |
AC |
321 ms |
6556 KB |
40_bad_maxcase_01.txt |
AC |
74 ms |
1948 KB |
40_bad_maxcase_02.txt |
AC |
71 ms |
2080 KB |
40_bad_maxcase_03.txt |
AC |
69 ms |
2084 KB |
40_bad_maxcase_04.txt |
AC |
74 ms |
1956 KB |
40_bad_maxcase_05.txt |
AC |
67 ms |
2080 KB |
41_bad_shufflecase_01.txt |
AC |
72 ms |
1952 KB |
41_bad_shufflecase_02.txt |
AC |
69 ms |
1952 KB |
41_bad_shufflecase_03.txt |
AC |
70 ms |
2080 KB |
41_bad_shufflecase_04.txt |
AC |
71 ms |
1836 KB |