oj.uz

Submission #1109037

# Submission time Handle Problem Language Result Execution time Memory
1109037 2024-11-05T21:25:23 Z Ludissey Wall (IOI14_wall) C++17
61 / 100
 791 ms 262144 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int n,q; 
vector<pair<pair<int,int>,int>> qrs;



struct node {
    node* left;
    node* right;
    int sum=0;
    int lazy=-1;
    bool lazyOP=0;
    int lazy2=-1;
    bool lazy2OP=0;
    void update(){
      sum=left->sum+right->sum;
    }
};
 
struct segtree {
  int n;
  node* root=new node{nullptr,nullptr,0,-1,false,-1,false};

  void add(node* x, int v, bool t){
    if(x->lazy<0){
      x->lazyOP=t;
      x->lazy=v;
    }else if(x->lazy2<0) {
      if(x->lazyOP==t) {
        if(t==0) x->lazy=max(x->lazy,v);
        else x->lazy=min(x->lazy,v);
      }else{
        x->lazy2OP=t;
        x->lazy2=v;
      }
    }else if(x->lazy2OP==t){
      if(t==0) x->lazy2=max(x->lazy2,v);
      else x->lazy2=min(x->lazy2,v);
    }else{
      if(t==0) {
        if(x->lazy2<=v){
          x->lazy=x->lazy2;
          x->lazyOP=x->lazy2OP;
          x->lazy2=v;
          x->lazy2OP=t;
        }else{
          if(x->lazy2>x->lazy) x->lazy=max(x->lazy,v);
        }
      }
      else {
        if(x->lazy2>=v){
          x->lazy=x->lazy2;
          x->lazyOP=x->lazy2OP;
          x->lazy2=v;
          x->lazy2OP=t;
        }else{
          if(x->lazy2<x->lazy) x->lazy=min(x->lazy,v);
        }
      }
    }
  }

  void propagate(node* x){
    if(x->lazy>-1){
      if(x->left==nullptr){
        if(x->lazyOP==0) x->sum=max(x->sum,x->lazy);
        else x->sum=min(x->sum,x->lazy);
        if(x->lazy2>-1){
          if(x->lazy2OP==0) x->sum=max(x->sum,x->lazy2);
          else x->sum=min(x->sum,x->lazy2);
          x->lazy2=-1;
        }
        x->lazy=-1;
        return;
      }
      if(x->lazy2>-1){
        add(x->left,x->lazy,x->lazyOP);
        add(x->right,x->lazy,x->lazyOP);
        x->lazy=x->lazy2;
        x->lazyOP=x->lazy2OP;
        x->lazy2=-1;
      }
      add(x->left,x->lazy,x->lazyOP);
      add(x->right,x->lazy,x->lazyOP);
      x->lazy=-1;
    }
  }

  void updateMN(node* x, int l, int r, int qL, int qR, int v){
    if(l>qR||r<qL) return;
    propagate(x);
    if(l>=qL&&r<=qR){
      add(x,v,1);
      return;
    }
    int mid=(l+r)/2;
    updateMN(x->left,l,mid,qL,qR,v);
    updateMN(x->right,mid+1,r,qL,qR,v);
    x->update();
  }

  void updateMX(node* x, int l, int r, int qL, int qR, int v){
    if(l>qR||r<qL) return;
    propagate(x);
    if(l>=qL&&r<=qR){
      add(x,v,0);
      return;
    }
    int mid=(l+r)/2;
    updateMX(x->left,l,mid,qL,qR,v);
    updateMX(x->right,mid+1,r,qL,qR,v);
    x->update();
  }

  void build(node* x, int l, int r){
    if(l==r){
        x->sum=0;
        return;
    }
    int mid=(l+r)/2;
    x->left=new node{nullptr,nullptr,0,-1,false,-1,false};
    x->right=new node{nullptr,nullptr,0,-1,false,-1,false};
    build(x->left,l,mid);
    build(x->right,mid+1,r);
    x->update();
  }
  int query(node* x, int l, int r, int p){
    if(r<p||l>p) return -1e9;
    propagate(x);
    if(l==p&&r==p) return x->sum;
    int mid=(l+r)/2;
    if(mid>=p) return query(x->left,l,mid,p); 
    else return query(x->right,mid+1,r,p);
  }
  void updateMN(int l, int r, int v){
    updateMN(root,0,n-1,l,r,v);
  }
  void updateMX(int l, int r, int v){
    updateMX(root,0,n-1,l,r,v);
  }
  int query(int p){
    return query(root,0,n-1,p);
  }
  segtree(int x){
    n=x;
    build(root,0,n-1);
  }
};

void buildWall(signed _n, signed _k, signed _op[], signed _left[], signed _right[], signed _height[], signed finalHeight[]){
  n=_n; q=_k;
  qrs.resize(q);
  segtree seg(n);

  for (int i = 0; i < q; i++)
  {
    int l=_left[i]; int r=_right[i];
    if(_op[i]==1) seg.updateMX(l,r,_height[i]);
    else seg.updateMN(l,r,_height[i]);
  }
  for (int i = 0; i < n; i++) finalHeight[i]=seg.query(i);
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 1872 KB Output is correct
5 Correct 6 ms 2044 KB Output is correct
6 Correct 5 ms 1872 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 112 ms 19784 KB Output is correct
3 Correct 170 ms 14008 KB Output is correct
4 Correct 532 ms 42056 KB Output is correct
5 Correct 205 ms 41544 KB Output is correct
6 Correct 200 ms 40520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 2044 KB Output is correct
5 Correct 6 ms 1872 KB Output is correct
6 Correct 5 ms 1820 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 91 ms 23072 KB Output is correct
9 Correct 167 ms 13896 KB Output is correct
10 Correct 535 ms 33048 KB Output is correct
11 Correct 186 ms 33608 KB Output is correct
12 Correct 198 ms 33552 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 85 ms 19960 KB Output is correct
15 Correct 39 ms 3800 KB Output is correct
16 Correct 734 ms 33280 KB Output is correct
17 Correct 203 ms 42312 KB Output is correct
18 Correct 192 ms 42312 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 9 ms 1924 KB Output is correct
5 Correct 5 ms 2128 KB Output is correct
6 Correct 5 ms 2040 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 96 ms 19784 KB Output is correct
9 Correct 158 ms 14408 KB Output is correct
10 Correct 495 ms 38216 KB Output is correct
11 Correct 201 ms 41452 KB Output is correct
12 Correct 204 ms 33476 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 95 ms 19860 KB Output is correct
15 Correct 38 ms 4388 KB Output is correct
16 Correct 791 ms 38472 KB Output is correct
17 Correct 206 ms 42312 KB Output is correct
18 Correct 222 ms 42312 KB Output is correct
19 Runtime error 348 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -