#include<stdio.h>
#include<algorithm>
using namespace std;
struct SegTree{
SegTree *c1, *c2;
int S;
SegTree(){
c1=c2=NULL;
S=0;
}
};
long long L;
int cnt, n, Q;
struct Query{
int b, e, ck;
bool operator<(const Query &p)const{
return b<p.b;
}
}w[5], tw[5];
void AddQ(long long b, long long e){
if(b<0)b+=2*L,e+=2*L;
b%=(2*L),e%=(2*L);
if(b>e)e+=2*L;
if(e>=2*L){
w[cnt].b=b,w[cnt].e=2*L-1;cnt++;
w[cnt].b=0,w[cnt].e=e-2*L;cnt++;
return;
}
w[cnt].b=b,w[cnt].e=e;cnt++;
}
SegTree *Root;
void Ins(SegTree *nd, int b, int e, int x, int y){
if(b==e){
nd->S+=y;
return;
}
int m = b+(e-b)/2;
if(x <= m){
if(!nd->c1)nd->c1 = new SegTree();
Ins(nd->c1,b,m,x,y);
}
else{
if(!nd->c2)nd->c2 = new SegTree();
Ins(nd->c2,m+1,e,x,y);
}
nd->S=0;
if(nd->c1)nd->S += nd->c1->S;
if(nd->c2)nd->S += nd->c2->S;
}
int Gap(SegTree *nd, int b, int e, int s, int l){
if(b==s&&e==l){
return nd->S;
}
int m = b+(e-b)/2, r = 0;
if(nd->c1 && s <= m)r += Gap(nd->c1,b,m,s,min(m,l));
if(nd->c2 && l > m)r += Gap(nd->c2,m+1,e,max(m+1,s),l);
return r;
}
int Pro(long long mid, long long t){
int s = 0, tc = 0;
cnt = 0;
if(mid < L){
AddQ(-t,-t+mid);
if(mid)AddQ(2*L-mid-t,2*L-t-1);
}
else if(mid > L){
AddQ(-t,-t+2*L-mid);
AddQ(-t+mid,-t+L*2-1);
}
else AddQ(0,2*L-1);
sort(w,w+cnt);
for(i=0;i<cnt;i++){
if(i==0 || w[i].b != w[i-1].e+1)tw[tc].b = w[i].b;
if(i==cnt-1 || w[i].e+1!=w[i+1].b)tw[tc++].e=w[i].e;
}
s=0;
for(int i=0;i<tc;i++){
s += Gap(Root,0,2*L-1,tw[i].b,tw[i].e);
}
return s;
}
int Rank[601][1010], In[201000], SZ[601], MM;
int TP[201000];
void init(){
int i, j, cnt = 0, pv = 1, tt;
for(i=1;i<=MM;i++){
for(j=1;j<=SZ[i];j++)TP[++cnt]=Rank[i][j];
SZ[i]=0;
}
tt = (cnt-1)/600+1;
for(i=1;i<=cnt;i++){
if(SZ[pv] == tt)pv++;
Rank[pv][++SZ[pv]] = TP[i];
In[TP[i]]=pv;
}
MM = pv;
}
void UDT(int a, int r){
if(!MM){
MM++;
Rank[1][++SZ[1]] = a;
In[a] = 1;
return;
}
int i, x, rr = r;
for(i=1;i<=MM;i++){
if(SZ[i]+1>=r)break;
r-=SZ[i];
}
x = i;
if(SZ[x] == 800){
init();
UDT(a,rr);
return;
}
for(i=SZ[x];i>=r;i--)Rank[x][i+1]=Rank[x][i];
Rank[x][r] = a;
SZ[x]++;
In[a] = x;
}
int Get(int a){
int x = In[a], i, c = 0;
for(i=1;i<x;i++)c+=SZ[i];
for(i=1;i<=SZ[x];i++){
if(Rank[x][i]==a)break;
}
return c+i;
}
int main(){
int r, p, b;
long long t,be, ed, mid;
long long a;
scanf("%lld%d",&L,&Q);
Root = new SegTree();
while(Q--){
scanf("%lld%d%lld",&t,&p,&a);
t%=(2*L);
if(p==1){
scanf("%d",&b);
if(b == -1)a = 2*L-a;
n++;
UDT(n, Pro(a,t)+1);
a=(a-t+2*L)%(2*L);
Ins(Root, 0, 2*L-1, a, 1);
}
if(p==2){
a = Get(a);
be = 0, ed = L-1, r = L;
while(be<=ed){
mid=(be+ed)>>1;
if(Pro(mid,t) >= a){
r= mid;
ed=mid-1;
}
else be=mid+1;
}
printf("%d\n",r);
}
}
}
Compilation message
X.cpp: In function ‘int Pro(long long int, long long int)’:
X.cpp:75:9: error: ‘i’ was not declared in this scope
for(i=0;i<cnt;i++){
^
X.cpp: In function ‘int main()’:
X.cpp:141:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%d",&L,&Q);
^
X.cpp:144:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%d%lld",&t,&p,&a);
^
X.cpp:147:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b);
^
