| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 830649 | 2023-08-19T08:52:36 Z | Amylopectin | Abracadabra (CEOI22_abracadabra) | C++14 | 436 ms | 27488 KB |
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int mxn = 4e6 + 10;
struct we
{
int tt,ii,idx,vall;
};
bool cmp(const struct we &l,const struct we &r)
{
return l.tt < r.tt;
}
bool cmp2(const struct we &l,const struct we &r)
{
return l.idx < r.idx;
}
struct we sot[mxn] = {};
int ta[mxn] = {},fa[mxn] = {},u[mxn] = {},li[mxn] = {},cma = 0,se[mxn] = {}
,fipo,lef,mat[mxn] = {},va[mxn] = {},poi[mxn] = {},stac[mxn] = {};
int ad(int cl,int cr,int no,int tar,int ava)
{
if(cl > tar || cr < tar)
{
return 0;
}
if(cl == cr)
{
se[no] = ava;
return 0;
}
int mid = (cl+cr) / 2;
ad(cl,mid,no*2,tar,ava);
ad(mid+1,cr,no*2+1,tar,ava);
se[no] = se[no*2] + se[no*2+1];
return 0;
}
int fii(int cl,int cr,int no,int fiva)
{
if(cl == cr)
{
fipo = cl;
lef = fiva;
return 0;
}
int mid = (cl+cr) / 2;
if(se[no*2] < fiva)
{
fiva -= se[no*2];
fii(mid+1,cr,no*2+1,fiva);
}
else
{
fii(cl,mid,no*2,fiva);
}
return 0;
}
int main()
{
freopen("t7.out","w",stdout);
int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
scanf("%d %d",&n,&q);
stac[0] = n+1;
for(i=1; i<=n; i++)
{
poi[i] = -1;
}
for(i=0; i<n; i++)
{
scanf("%d",&ta[i]);
mat[ta[i]] = i;
while(stac[tst] < ta[i])
{
poi[stac[tst]] = ta[i];
tst --;
}
tst ++;
stac[tst] = ta[i];
}
for(i=0; i<q; i++)
{
scanf("%d %d",&cn,&cm);
sot[i] = {cn,cm,i,-1};
}
cbe = ta[0];
bep = 0;
for(i=1; i<n/2; i++)
{
if(ta[i] > cbe)
{
va[cbe] = i-bep;
ad(1,n,1,cbe,i-bep);
bep = i;
cbe = ta[i];
}
}
va[cbe] = n/2-bep;
ad(1,n,1,cbe,n/2-bep);
bep = n/2;
cbe = ta[n/2];
for(i=n/2+1; i<n; i++)
{
if(ta[i] > cbe)
{
va[cbe] = i-bep;
ad(1,n,1,cbe,i-bep);
bep = i;
cbe = ta[i];
}
}
va[cbe] = n-bep;
ad(1,n,1,cbe,n-bep);
sort(sot,sot+q,cmp);
// for(j=0; j<n; j++)
// {
// printf("%d ",ta[j]);
// }
// printf("\n");
// re(-1,n,0);
// printf("%d\n",cma);
ru = 0;
while(ru < q && sot[ru].tt == 0)
{
sot[ru].vall = ta[sot[ru].ii-1];
ru ++;
}
for(i=1; i<=n; i++)
{
while(ru < q && sot[ru].tt == i)
{
fii(1,n,1,sot[ru].ii);
sot[ru].vall = ta[mat[fipo]+lef-1];
ru ++;
}
if(ru == q)
{
break;
}
fii(1,n,1,n/2);
cn = fipo;
cm = lef;
clim = mat[cn] + va[cn];
if(va[cn] == cm)
{
break;
}
ad(1,n,1,cn,lef);
va[cn] = lef;
cn = ta[mat[cn]+lef];
while(1)
{
fn = poi[cn];
if(fn == -1)
{
break;
}
if(mat[fn] >= clim)
{
break;
}
ad(1,n,1,cn,mat[fn] - mat[cn]);
va[cn] = mat[fn] - mat[cn];
cn = fn;
}
// fn =
// fm = va[cn] - lef;
ad(1,n,1,cn,clim - mat[cn]);
va[cn] = clim - mat[cn];
// va[fn] = fm;
// cl = 0;
// cr = n/2;
// for(j=0; j<n; j++)
// {
// if(cl == n/2)
// {
// fa[j] = ta[cr];
// cr ++;
// }
// else if(cr == n)
// {
// fa[j] = ta[cl];
// cl ++;
// }
// else if(ta[cl] < ta[cr])
// {
// fa[j] = ta[cl];
// cl ++;
// }
// else
// {
// fa[j] = ta[cr];
// cr ++;
// }
// }
// for(j=0; j<n; j++)
// {
// ta[j] = fa[j];
// // printf("%d ",fa[j]);
// }
// while(ru < q && sot[ru].tt == i)
// {
// fii(1,n,1,sot[ru].ii);
// sot[ru].vall = ta[mat[fipo]+lef-1];
// ru ++;
// }
// if(ru == q)
// {
// break;
// }
// printf("\n");
}
while(ru < q)
{
fii(1,n,1,sot[ru].ii);
sot[ru].vall = ta[mat[fipo]+lef-1];
ru ++;
}
sort(sot,sot+q,cmp2);
for(i=0; i<q; i++)
{
printf("%d\n",sot[i].vall);
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 408 ms | 20044 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 436 ms | 27488 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 95 ms | 5324 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 408 ms | 20044 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |