oj.uz

Submission #180299

# Submission time Handle Problem Language Result Execution time Memory
180299 2020-01-08T17:35:08 Z FieryPhoenix Wall (IOI14_wall) C++11
0 / 100
 669 ms 13948 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007


struct LazySegmentTree{
  int siz;
  vector<ll>tree,lazyAdd,lazySub,priOp;
  LazySegmentTree(int temp){
    siz=temp;
    while ((siz&(siz-1))!=0) siz++;
    for (int i=0;i<siz*2;i++){
      tree.push_back(0);
      lazyAdd.push_back(-INF);
      lazySub.push_back(INF);
      priOp.push_back(1);
    }
  }
  void calc(int node){
    if (priOp[node]==2){
      tree[node]=max(tree[node],lazyAdd[node]);
      tree[node]=min(tree[node],lazySub[node]);
    }
    else{
      tree[node]=min(tree[node],lazySub[node]);
      tree[node]=max(tree[node],lazyAdd[node]);
    }
  }
  void propagate(int node, int L, int R){
    calc(node);
    if (L!=R){
      calc(node*2);
      calc(node*2+1);
      if (priOp[node]==2){
	applyAdd(node*2,lazyAdd[node]);
	applySub(node*2,lazySub[node]);
	applyAdd(node*2+1,lazyAdd[node]);
	applySub(node*2+1,lazySub[node]);
      }
      else{
	applySub(node*2,lazySub[node]);
	applyAdd(node*2,lazyAdd[node]);
	applySub(node*2+1,lazySub[node]);
	applyAdd(node*2+1,lazyAdd[node]);
      }
      calc(node*2);
      calc(node*2+1);
    }
    lazyAdd[node]=-INF;
    lazySub[node]=INF;
  }
  void applyAdd(int node, ll x){
    priOp[node]=1;
    if (x>lazyAdd[node]){
      lazyAdd[node]=x;
      lazySub[node]=INF;
    }
  }
  void applySub(int node, ll x){
    priOp[node]=2;
    if (x<=lazySub[node])
      lazySub[node]=x;
  }
  void update(int node, int L, int R, int i, int j, ll x, int type){
    propagate(node,L,R);
    if (L>R || L>j || R<i)
      return;
    if (L>=i && R<=j){
      if (type==1)
	applyAdd(node,x);
      else
	applySub(node,x);
      propagate(node,L,R);
      return;
    }
    update(node*2,L,(L+R)/2,i,j,x,type);
    update(node*2+1,(L+R)/2+1,R,i,j,x,type);
    //tree[node]=tree[node*2]+tree[node*2+1];
  }
  ll query(int node, int L, int R, int i,int j){
    if (L>R || L>j || R<i)
      return 0;
    propagate(node,L,R);
    //cout<<"QPOP "<<node<<endl;
    if (L>=i && R<=j){
      //cout<<"FOUND "<<node<<endl;
      return tree[node];
    }
    ll q1=query(node*2,L,(L+R)/2,i,j);
    ll q2=query(node*2+1,(L+R)/2+1,R,i,j);
    return q1+q2;
  }
  ll query(int i, int j){ return query(1,0,siz-1,i,j); }
  void update(int i, int j, ll val, int type){ update(1,0,siz-1,i,j,val,type); }
};

void buildWall(int N, int K, int op[], int l[], int r[], int h[], int finalh[]){
  LazySegmentTree lst=LazySegmentTree(N);
  for (int i=0;i<K;i++){
    lst.update(l[i],r[i],h[i],op[i]);
    /*
    bool debug=false;
    if (debug){
      cout<<"BEFORE: "<<endl;
      for (int j=1;j<lst.siz*2;j++)
	cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
    }
    for (int j=0;j<N;j++)
      cout<<lst.query(j,j)<<' ';
    cout<<endl;
    if (debug){
      cout<<"AFTER: "<<endl;
      for (int j=1;j<lst.siz*2;j++)
	cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
    }
    */
  }
  for (int i=0;i<N;i++)
    finalh[i]=lst.query(i,i);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Incorrect 6 ms 532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 172 ms 13948 KB Output is correct
3 Incorrect 669 ms 9696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Incorrect 10 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -