//#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ 500
int n, l;
int loc[150005];
int bid[150005];
vector<vector<pair<int , pii> > > buck;
//{LOC {count, last} }
inline int find(){
int res = 0;
int lst = -1;
for(auto& v : buck){
if(v.empty() || v.back().ff <= lst) continue;
int id = upper_bound(v.begin(), v.end(), lst, [](const int& lhs, const pair<int, pii>& rhs){
return lhs < rhs.ff;
}) - v.begin();
res += v[id].ss.ff;
lst = v[id].ss.ss;
}
return res;
}
inline void recalc(vector<pair<int, pii> >& vec){
int sz = vec.size();
int r = sz;
for(int l = sz - 1; l >= 0; l--){
while(vec[r - 1].ff > vec[l].ff + ::l) r--;
vec[l].ss.ff = (r == sz ? 0 : vec[r].ss.ff) + 1;
vec[l].ss.ss = (r == sz ? vec[l].ff + ::l : vec[r].ss.ss);
}
}
vector<pii> sorted;
inline void renew(int o){
for(int i = 0; i < n; i++){
sorted[i].ff = loc[i];
sorted[i].ss = i;
}
if(!o){
sort(sorted.begin(), sorted.end());
}
buck.clear();
buck.resize((n - 1) / SQ + 1);
for(int i = 0; i < n; i++){
buck[i / SQ].push_back({sorted[i].ff, {0, 0}});
bid[sorted[i].ss] = i / SQ;
}
for(auto& x : buck){
recalc(x);
}
}
void init(int N, int L, int X[]){
n = N; l = L;
for(int i = 0; i < n; i++){
loc[i] = X[i];
}
sorted.resize(n);
renew(1);
}
int cnt = 0;
inline void erase(vector<pair<int, pii> >& buck, int& x){
for(int i = 1; i < buck.size(); i++){
if(buck[i - 1].ff == x) swap(buck[i - 1], buck[i]);
}
buck.pop_back();
recalc(buck);
}
inline void insert(vector<pair<int, pii> >& buck, int& x){
buck.push_back({x, {0, 0}});
int i = buck.size() - 1;
while(i != 0 && buck[i - 1].ff > buck[i].ff){
swap(buck[i - 1], buck[i]);
i--;
}
recalc(buck);
}
int update(int j, int y){
if(loc[j] == y) return find();
if(++cnt % SQ == 0){
loc[j] = y;
renew(0);
} else {
erase(buck[bid[j]], loc[j]);
int t = upper_bound(buck.begin(), buck.end(), y, [](const int& lhs, const vector<pair<int, pii> >& rhs){
return rhs.back().ff >= lhs;
}) - buck.begin();
if(t == buck.size()) t--;
insert(buck[t], y);
loc[j] = y;
bid[j] = t;
}
return find();
}
#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];
void read_input()
{
int i;
scanf("%d %d %d",&N,&L,&M);
for(i=0; i<N; i++)
scanf("%d",&X[i]);
for(i=0; i<M; i++)
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 erase(std::vector<std::pair<int, std::pair<int, int> > >&, int&)':
elephants.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < buck.size(); i++){
~~^~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:93:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(t == buck.size()) t--;
~~^~~~~~~~~~~~~~
elephants.cpp: In function 'void read_input()':
elephants.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&N,&L,&M);
~~~~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&X[i]);
~~~~~^~~~~~~~~~~~
elephants.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&ii[i],&yy[i],&sol[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc6PSUNl.o: In function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'
/tmp/ccAFKrVp.o:elephants.cpp:(.text+0x30): first defined here
/tmp/cc6PSUNl.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAFKrVp.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
