Pagini recente » Cod sursa (job #47857) | Cod sursa (job #2812151) | Cod sursa (job #2460288) | Cod sursa (job #2138823) | Cod sursa (job #1869390)
#include <iostream>
#include <fstream>
#define N 100000
using namespace std;
ifstream in("hotel.in");
ofstream out("hotel.out");
int n, p;
struct Node{int mxl, mxr, mxc;}sgt[N*3+5];
void update(int l, int r, int ul, int ur, int node, int o){
if(ul<=l&&r<=ur){
if(o==1)sgt[node].mxc=sgt[node].mxl=sgt[node].mxr=0;
else sgt[node].mxc=sgt[node].mxl=sgt[node].mxr=r-l+1;
return;
}
int m=(l+r)/2;
if(sgt[node].mxc==r-l+1){
sgt[node*2].mxc=sgt[node*2].mxl=sgt[node*2].mxr=m-l+1;
sgt[node*2+1].mxc=sgt[node*2+1].mxl=sgt[node*2+1].mxr=r-m;
}
if(!sgt[node].mxc){
sgt[node*2].mxc=sgt[node*2].mxl=sgt[node*2].mxr=0;
sgt[node*2+1].mxc=sgt[node*2+1].mxl=sgt[node*2+1].mxr=0;
}
if(ul<=m)update(l, m, ul, ur, node*2, o);
if(ur>m)update(m+1, r, ul, ur, node*2+1, o);
if(sgt[node*2].mxl==m-l+1)sgt[node].mxl=sgt[node*2].mxl+sgt[node*2+1].mxl;
else sgt[node].mxl=sgt[node*2].mxl;
if(sgt[node*2+1].mxr==r-m)sgt[node].mxr=sgt[node*2].mxr+sgt[node*2+1].mxr;
else sgt[node].mxr=sgt[node*2+1].mxr;
sgt[node].mxc=max(max(sgt[node*2].mxc, sgt[node*2+1].mxc),sgt[node*2].mxr+sgt[node*2+1].mxl);
}
int main(){
in>>n>>p;
int x, y, z;
sgt[1].mxc=sgt[1].mxl=sgt[1].mxr=n;
for(int i=1; i<=p; i++){
in>>x;
if(x==3){
out<<sgt[1].mxc<<"\n";
}else{
in>>y>>z;
update(1, n, y, y+z-1, 1, x);
}
}
return 0;
}