| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 550079 | neki | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vc vector
#define ps push_back
const int mm=350;
int n, l;
struct e{
int i, pos, val, odsek, kok;
e(int i_, int pos_): i(i_), pos(pos_){}
bool operator<(const e& oth){return pos < oth.pos;}
};
vc<e> es;
vc<vc<e*>> dp;
void calcdp(vc<e*>& arr){
int siz=arr.size(), nas=siz;
if(siz==0) return;
for(int i=siz-1;i>=0;--i){
while((*arr[i]).pos+l<= (*arr[nas-1]).pos) --nas;
if(nas<siz) (*arr[i]).val=(*arr[nas]).val, (*arr[i]).kok=(*arr[nas]).kok + 1;
else (*arr[i]).val=(*arr[i]).pos+l, (*arr[i]).kok=1;
}
}
void build(){
vc<e*> vsi;
for(auto v : dp) for(auto u : v ) vsi.push_back(u);
dp.clear();
for(int ods=0;ods<n;ods+=mm){
vc<e*> nods;
for(int i=ods;i<min(n, ods+mm);++i){(*vsi[i]).odsek=ods/mm;nods.ps(vsi[i]);}
calcdp(nods);
dp.ps(nods);
}
}
void init(int N, int L, int* X){
n=N, l=L+1;
for(int i=0;i<n;++i) es.ps(e(i, X[i]));
dp.ps({});
for(int i=0;i<n;++i)dp[0].ps(&es[i]);
build();
}
void printdp(){
for(auto&& u:dp){
for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
}
}
int update(int ind, int y){
es[ind].pos=y;
int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<(*(dp[i].back())).pos){nov=i;break;}
int star = es[ind].odsek;
if(nov!=star){
assert(star<dp.size());
vc<e*> shrani=dp[star];
dp[star].clear();
for(auto v : shrani) if((*v).i != ind) dp[star].ps(v);
calcdp(dp[star]);
dp[nov].ps(&es[ind]);
}
//printdp();
sort(dp[nov].begin(), dp[nov].end(), [](e* a, e* b){
return (*a)<(*b);
});
calcdp(dp[nov]);
//printdp();
int curpos=-1, ret=0;
for(auto&& v: dp) if(v.size()>0 and curpos<=(*(v.back())).pos){
int L=0, R=v.size()-1; //nani
while(L<R){
int mid=(L+R)/2;
if(curpos <= (*v[mid]).pos) R=mid;
else L=mid+1;
}
curpos= (*v[L]).val;
ret+= (*v[L]).kok;
}
return ret;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000000
#define MAX_M 1000000
static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&L,&M));
for(i=0; i<N; i++)
my_assert(1==scanf("%d",&X[i]));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}
int main()
{
int i, ans;
read_input();
init(N,L,X);
for(i=0; i<M; i++) {
ans = update(ii[i],yy[i]);
if(ans==sol[i])continue;
printf("Incorrect. In %d-th move, answered %d (%d expected).\n",
i+1, ans, sol[i]);
return 0;
}
printf("Correct.\n");
return 0;
}