Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
using namespace std; ifstream cin("hotel.in"); ofstream cout("hotel.out"); const int mxN = 1e5; struct node{int sum=0, pref, suf, flag;}A[4*mxN+1]; void printInfo(int node, int st, int dr) { cout << "st = " << st << " dr = " << dr << '\n'; cout << "sum = " << A[node].sum << '\n'; cout << "pref = " << A[node].pref << ' ' << " suf = " << A[node].suf << '\n'; cout << "flag = " << A[node].flag << '\n'; } void build(int node, int st ,int dr) { if(st == dr) { A[node] = {1,1,1,0}; return; } int mid = (st + dr) / 2; build(2*node,st,mid); build(2*node+1,mid+1,dr); int val = A[2*node].sum + A[2*node+1].sum; A[node] = {val,val,val,0}; } void update(int node , int st, int dr, int a , int b, int val) { if(a<=st && dr <= b) { if(val == 1) // se ocupa intervalul. A[node] = {0,0,0,1}; if(val == 0) // se elibera intervalul { int len = dr - st + 1; A[node] = {len,len,len,2}; } //printInfo(node,st,dr); return; } int mid = (st + dr) / 2; int lenSt = mid - st + 1, lenDr = dr - mid; if(A[node].flag == 1) A[2*node] = A[2*node+1] = {0,0,0,1}, A[node].flag = 0; if(A[node].flag == 2) { A[node].flag = 0; A[2*node] = {lenSt,lenSt,lenSt, 2}; A[2*node+1] = {lenDr,lenDr,lenDr,2}; } if(a<=mid) update(2*node,st,mid,a,b,val); if(b>mid) update(2*node+1,mid+1,dr,a,b,val); // dam update la intervalul combinat A[node].pref = A[2*node].pref; if(A[node].pref == lenSt) A[node].pref += A[2*node+1].pref; A[node].suf = A[2*node+1].suf; if(A[node].suf == lenDr) A[node].suf += A[2*node].suf; A[node].sum = max(A[2*node].sum, A[2*node+1].sum); A[node].sum = max(A[node].sum, A[2*node].suf + A[2*node+1].pref); //printInfo(node,st,dr); } int main() { int n , m; cin >> n >> m; build(1,1,n); for(int i = 1;i<=m;i++) { //cout << "QUERY :"; int op; cin >> op; if(op == 1) { int a , b; cin >> a >> b; update(1,1,n,a,a + b - 1,1); } if(op == 2) { int a, b; cin >> a >> b; update(1,1,n,a,a + b - 1,0); } if(op == 3) { cout << A[1].sum << '\n'; } } return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)