Submission #980061
Source Code Expand
#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
typedef complex<double> P;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD = 1000000007;
struct segtree {
lli N;
vector<lli> dat, sum;
segtree(lli n)
{
N = 1;
while (N < n)
N <<= 1;
dat.assign(2 * N - 1, 0);
sum.assign(2 * N - 1, 0);
}
void add(lli a, lli b, lli x)
{
add(a, b, x, 0, 0, N);
}
lli add(lli a, lli b, lli x, lli k, lli l, lli r)
{
if (b <= l or r <= a)
return dat[k];
if (a <= l and r <= b) {
sum[k] += x;
return dat[k] += x;
}
lli m = (l + r) / 2;
return dat[k] = min(add(a, b, x, 2 * k + 1, l, m), add(a, b, x, 2 * k + 2, m, r)) + sum[k];
}
lli minimum(lli a, lli b) { return minimum(a, b, 0, 0, N); }
lli minimum(lli a, lli b, lli k, lli l, lli r)
{
if (b <= l or r <= a)
return 1e9;
if (a <= l and r <= b)
return dat[k];
lli m = (l + r) / 2;
return min(minimum(a, b, 2 * k + 1, l, m), minimum(a, b, 2 * k + 2, m, r)) + sum[k];
}
lli get(lli i)
{
return minimum(i, i + 1);
}
};
segtree a(20005);
segtree b(20005);
lli n;
lli p[20005];
void ok(){
lli last = a.get(p[0])+ b.get(p[0]);
for(lli i = 1;i<n;i++){
if(last >= a.get(p[i])+ b.get(p[i])){
if(p[i] > p[i-1]){
a.add(p[i],n,last - a.get(p[i])- b.get(p[i]) + 2);
}
else{
b.add(0,p[i]+1,last - a.get(p[i])- b.get(p[i]) + 2);
}
}
last = a.get(p[i])+ b.get(p[i]);
}
}
int main()
{
cin >> n;
rep(i,n){
cin >> p[i];
p[i]--;
}
rep(i,n)a.add(i,i+1,i+1);
rep(i,n)b.add(n - i - 1,n-i, i+1);
ok();
ok();
rep(i,n)cout << a.get(i) << ' ';
cout << endl;
rep(i,n)cout << b.get(i)<<' ';
}
Submission Info
Submission Time |
|
Task |
B - Construct Sequences |
User |
uenoku |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2594 Byte |
Status |
WA |
Exec Time |
50 ms |
Memory |
2816 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt, example2.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, example0.txt, example1.txt, example2.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
WA |
8 ms |
2304 KB |
001.txt |
WA |
7 ms |
2304 KB |
002.txt |
WA |
7 ms |
2304 KB |
003.txt |
WA |
6 ms |
2304 KB |
004.txt |
WA |
8 ms |
2304 KB |
005.txt |
WA |
49 ms |
2816 KB |
006.txt |
WA |
13 ms |
2432 KB |
007.txt |
WA |
44 ms |
2816 KB |
008.txt |
WA |
27 ms |
2560 KB |
009.txt |
WA |
47 ms |
2816 KB |
010.txt |
WA |
49 ms |
2816 KB |
011.txt |
WA |
49 ms |
2816 KB |
012.txt |
WA |
49 ms |
2816 KB |
013.txt |
WA |
49 ms |
2816 KB |
014.txt |
WA |
50 ms |
2816 KB |
015.txt |
WA |
41 ms |
2688 KB |
016.txt |
WA |
41 ms |
2688 KB |
017.txt |
WA |
45 ms |
2688 KB |
018.txt |
WA |
46 ms |
2688 KB |
example0.txt |
AC |
5 ms |
2304 KB |
example1.txt |
AC |
5 ms |
2304 KB |
example2.txt |
AC |
5 ms |
2304 KB |