LEM4 - WHITE BLACK

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 10011
#define mod 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second

double const PI=4*atan(1);
double const oo = 1e19;

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

struct tree{
    int maxleft, maxright, length;
    tree(){};
    tree(int _ml, int _mr, int _l){
        maxleft = _ml, maxright = _mr, length = _l;
    }
};

tree empty = tree(0, 0, 0);

int n, m, number, u, v;
tree f[maxn * 4];

void update(int l, int r, int i, int so){
    if(u > r || v < l) return;
    int t = (r - l + 1) * so;
    if(u <= l && v >= r){
        f[i] = tree(t, t, t);
        return;
    }
  //  if(f[i].length == t) return;
    int mid = (l + r) / 2;
    if(f[i].length == 0){
        f[i + i] = empty;
        f[i + i + 1] = empty;
    }
    if(f[i].length == r - l + 1){
        f[i + i] = tree(mid - l + 1, mid - l + 1, mid - l + 1);
        f[i + i + 1] = tree(r - mid, r - mid, r - mid);
    }
    update(l, mid, i + i, so);
    update(mid + 1, r, i + i + 1, so);
    
    f[i].length = max(f[i + i].length, max(f[i + i + 1].length, f[i + i].maxright + f[i + i + 1].maxleft));
    if(f[i + i].maxleft == mid - l + 1) f[i].maxleft = f[i + i + 1].maxleft + mid - l + 1;
    else f[i].maxleft = f[i + i].maxleft;
    if(f[i + i + 1].maxright == r - mid) f[i].maxright = f[i + i].maxright + r - mid;
    else f[i].maxright = f[i + i + 1].maxright;
}

int main(){
    //freopen("input.in","r",stdin); 
    //freopen("output.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++) {
        u = 1, v = i;
        update(1, n, 1, 1);
    }
    //printf("%d.......\n",f[1].length);
    for(int i = 0; i < m; i++){
        scanf("%d",&number);
        if(number == 3) printf("%d\n",f[1].length);
        else{
            scanf("%d %d",&u,&v);
            number = 2 - number;
            update(1, n, 1, number);
        }
    }
     // getch();
}

Download