Submission #534100
Source Code Expand
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif
using namespace std;
namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define VV(T) vector<vector< T > >
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
v.assign(a, vector<T>(b, t));
}
template <class F, class T>
void convert(const F &f, T &t){
stringstream ss;
ss << f;
ss >> t;
}
#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()
#define MOD 1000000007LL
#define EPS 1e-8
template <class Tp>
struct fenwick_tree{
typedef unsigned size_type;
std::vector<Tp> bit;
fenwick_tree(){}
explicit fenwick_tree(size_type n){
init(n);
}
void init(size_type n){
bit.assign(n + 1, Tp());
}
Tp sum(size_type i) const{
Tp s = 0;
while(i){
s += bit[i];
i -= i & -i;
}
return s;
}
Tp summod(size_type i, Tp mod) const{
Tp s = 0;
while(i){
s = (s + bit[i]) % mod;
i -= i & -i;
}
if(s < 0){ s += mod; }
return s;
}
void add(size_type i, Tp x){
size_type sz = bit.size();
while(i < sz){
bit[i] += x;
i += i & -i;
}
}
void addmod(size_type i, Tp x, Tp mod){
size_type sz = bit.size();
x %= mod;
if(x < 0){ x += mod; }
while(i < sz){
bit[i] = (bit[i] + x) % mod;
i += i & -i;
}
}
void clear(){
bit.clear();
}
void swap(fenwick_tree &f){
bit.swap(f.bit);
}
};
LL calcinv(const vector<int> &v){
int n = v.size();
fenwick_tree<int> fw(n + 1);
LL ans = 0;
for(int i = 0; i < n; ++i){
ans += i - fw.sum(v[i]);
fw.add(v[i], 1);
}
return ans;
}
LL solve(){
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
for(int &x : a){ scanf("%d", &x); }
for(int &x : b){ scanf("%d", &x); }
vector<int> rg(n);
for(int i = 0; i < n; ++i){
if(a[i] < b[0]){ return -1; }
rg[i] = upper_bound(ALL(b), a[i]) - b.begin() - 1;
}
VV(int) pp(n);
for(int i = 0; i < n; ++i){
pp[rg[i]].push_back(i);
}
priority_queue<LL> pq;
vector<int> v(n);
for(int i = n - 1; i >= 0; --i){
for(int x : pp[i]){
pq.push(x);
}
if(pq.empty()){
return -1;
}
v[i] = pq.top() + 1;
pq.pop();
}
LL ans = calcinv(v);
return ans;
}
void mainmain(){
cout << solve() << endl;
}
}
int main() try{
// ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(4);
mainmain();
}
catch(...){}
Submission Info
Submission Time |
|
Task |
G - ケンドー |
User |
climpet |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
3444 Byte |
Status |
AC |
Exec Time |
110 ms |
Memory |
8224 KB |
Compile Error
./Main.cpp: In function ‘{anonymous}::LL {anonymous}::solve()’:
./Main.cpp:146:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:148:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int &x : a){ scanf("%d", &x); }
^
./Main.cpp:149:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int &x : b){ scanf("%d", &x); }
^
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 |
29 ms |
912 KB |
00_small_sample_01.txt |
AC |
25 ms |
924 KB |
00_small_sample_02.txt |
AC |
25 ms |
800 KB |
10_small_01.txt |
AC |
28 ms |
920 KB |
10_small_02.txt |
AC |
26 ms |
800 KB |
10_small_03.txt |
AC |
28 ms |
804 KB |
10_small_04.txt |
AC |
27 ms |
800 KB |
10_small_05.txt |
AC |
28 ms |
920 KB |
10_small_06.txt |
AC |
27 ms |
804 KB |
10_small_07.txt |
AC |
27 ms |
920 KB |
10_small_08.txt |
AC |
27 ms |
736 KB |
10_small_09.txt |
AC |
26 ms |
912 KB |
10_small_10.txt |
AC |
27 ms |
800 KB |
20_large_01.txt |
AC |
106 ms |
6168 KB |
20_large_02.txt |
AC |
107 ms |
6172 KB |
20_large_03.txt |
AC |
110 ms |
6292 KB |
20_large_04.txt |
AC |
110 ms |
6420 KB |
20_large_05.txt |
AC |
107 ms |
6296 KB |
20_large_06.txt |
AC |
107 ms |
6404 KB |
20_large_07.txt |
AC |
103 ms |
6044 KB |
20_large_08.txt |
AC |
108 ms |
6296 KB |
20_large_09.txt |
AC |
109 ms |
6424 KB |
20_large_10.txt |
AC |
103 ms |
6164 KB |
30_maxcase_01.txt |
AC |
93 ms |
8224 KB |
31_almost_maxcase_01.txt |
AC |
103 ms |
8100 KB |
31_almost_maxcase_02.txt |
AC |
101 ms |
7840 KB |
31_almost_maxcase_03.txt |
AC |
102 ms |
8108 KB |
31_almost_maxcase_04.txt |
AC |
103 ms |
8084 KB |
31_almost_maxcase_05.txt |
AC |
103 ms |
8100 KB |
40_bad_maxcase_01.txt |
AC |
96 ms |
7584 KB |
40_bad_maxcase_02.txt |
AC |
94 ms |
7460 KB |
40_bad_maxcase_03.txt |
AC |
99 ms |
7712 KB |
40_bad_maxcase_04.txt |
AC |
94 ms |
7452 KB |
40_bad_maxcase_05.txt |
AC |
95 ms |
7584 KB |
41_bad_shufflecase_01.txt |
AC |
107 ms |
7716 KB |
41_bad_shufflecase_02.txt |
AC |
107 ms |
7456 KB |
41_bad_shufflecase_03.txt |
AC |
107 ms |
7580 KB |
41_bad_shufflecase_04.txt |
AC |
106 ms |
7444 KB |