#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;
}
Compilation message
elephants.cpp: In function 'void printdp()':
elephants.cpp:56:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
56 | for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
| ^~~
elephants.cpp:56:82: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
56 | for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
| ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:62:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | 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;}
| ~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from elephants.cpp:1:
elephants.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | assert(star<dp.size());
| ~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccdOUOn6.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccvoDtZ3.o:elephants.cpp:(.text+0x5c0): first defined here
/usr/bin/ld: /tmp/ccdOUOn6.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvoDtZ3.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
