# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
287048 | andreiomd | Santa Claus (RMI19_santa) | C++11 | 1093 ms | 2684 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int NMAX = 96068 + 5;
int T;
int N, X[NMAX], V[NMAX];
bool H[NMAX];
int the_last_elf;
int ans[NMAX];
multiset < int > S;
int Keep = 0;
namespace InParser
{
static const int BSIZE = (1 << 16);
static int pos = (BSIZE - 1);
static char buff[BSIZE];
static inline char Char ()
{
++pos;
if(pos == BSIZE)
{
pos = 0;
int n = fread(buff, 1, BSIZE, stdin);
if(n != BSIZE)
for(int i = n; i < BSIZE; ++i)
buff[i] = 0;
}
return buff[pos];
}
inline int Int ()
{
int ans = 0;
for( ; ; )
{
char Ch = Char();
if(Ch >= '0' && Ch <= '9')
{
ans = (int)(Ch - '0');
break;
}
}
for( ; ; )
{
char Ch = Char();
if(Ch >= '0' && Ch <= '9')
ans = ans * 10 + (int)(Ch - '0');
else
break;
}
return ans;
}
};
static inline void Read ()
{
N = InParser :: Int();
for(int i = 1; i <= N; ++i)
X[i] = InParser :: Int();
the_last_elf = 0;
for(int i = 1; i <= N; ++i)
{
H[i] = InParser :: Int();
if(!H[i])
the_last_elf = i;
}
for(int i = 1; i < the_last_elf; ++i)
ans[i] = -1;
for(int i = 1; i <= N; ++i)
V[i] = InParser :: Int();
return;
}
static inline bool Check (int Destination, int Middle)
{
S.clear();
for(int i = 1; i < Middle; ++i)
if(H[i] == 0)
S.insert(V[i]);
else
{
auto it = S.lower_bound(V[i]);
if(it != S.end())
S.erase(it);
}
for(int i = Middle; i <= Destination; ++i)
if(H[i] == 0)
S.insert(V[i]);
for(int i = Middle; i <= Destination; ++i)
if(H[i] == 1)
{
auto it = S.lower_bound(V[i]);
if(it != S.end())
S.erase(it);
}
return (bool)(S.empty());
}
static inline int Go (int pos)
{
int Left = 1, Right = pos, ans = 0;
while(Left <= Right)
{
int Mid = (Left + Right) >> 1;
if(Check(pos, Mid))
ans = Mid, Left = Mid + 1;
else
Right = Mid - 1;
}
if(ans == 0)
return -1;
Keep = ans;
return ((X[pos] << 1) - X[ans]);
}
static inline void Solve ()
{
int last_i = 0;
for(int i = the_last_elf; i <= N; ++i)
{
ans[i] = Go(i);
if(ans[i] != -1)
{
last_i = i;
break;
}
}
for(int i = (last_i + 1); i <= N; ++i)
{
while(Keep < i && Check(i, Keep + 1))
++Keep;
ans[i] = ((X[i] << 1) - X[Keep]);
}
return;
}
static inline void Write ()
{
for(int i = 1; i <= N; ++i)
{
printf("%d", ans[i]);
if(i != N)
printf(" ");
}
printf("\n");
return;
}
static inline void TestCase ()
{
Read();
Solve();
Write();
return;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
/// freopen("santaclaus.in", "r", stdin);
/// freopen("santaclaus.out", "w", stdout);
T = InParser :: Int();
while(T--)
TestCase();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |