oj.uz

Submission #1109043

# Submission time Handle Problem Language Result Execution time Memory
1109043 2024-11-05T21:34:05 Z Ludissey Wall (IOI14_wall) C++17
100 / 100
 802 ms 230556 KB 
#include "wall.h"
#include <bits/stdc++.h>
#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){
    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 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 1576 KB Output is correct
5 Correct 5 ms 1360 KB Output is correct
6 Correct 5 ms 1360 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 109 ms 14036 KB Output is correct
3 Correct 159 ms 7752 KB Output is correct
4 Correct 498 ms 23880 KB Output is correct
5 Correct 190 ms 24392 KB Output is correct
6 Correct 187 ms 24392 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 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 1616 KB Output is correct
5 Correct 5 ms 1552 KB Output is correct
6 Correct 5 ms 1360 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 85 ms 13880 KB Output is correct
9 Correct 158 ms 7888 KB Output is correct
10 Correct 496 ms 23900 KB Output is correct
11 Correct 196 ms 24392 KB Output is correct
12 Correct 189 ms 24392 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 91 ms 13912 KB Output is correct
15 Correct 38 ms 2896 KB Output is correct
16 Correct 748 ms 24304 KB Output is correct
17 Correct 202 ms 24136 KB Output is correct
18 Correct 200 ms 24136 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 8 ms 1584 KB Output is correct
5 Correct 5 ms 1532 KB Output is correct
6 Correct 6 ms 1528 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 88 ms 13896 KB Output is correct
9 Correct 174 ms 7900 KB Output is correct
10 Correct 488 ms 23880 KB Output is correct
11 Correct 186 ms 24392 KB Output is correct
12 Correct 194 ms 24648 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 95 ms 14088 KB Output is correct
15 Correct 42 ms 2908 KB Output is correct
16 Correct 749 ms 24220 KB Output is correct
17 Correct 196 ms 24348 KB Output is correct
18 Correct 211 ms 24136 KB Output is correct
19 Correct 786 ms 230556 KB Output is correct
20 Correct 763 ms 227912 KB Output is correct
21 Correct 751 ms 230472 KB Output is correct
22 Correct 790 ms 228204 KB Output is correct
23 Correct 802 ms 228044 KB Output is correct
24 Correct 772 ms 228016 KB Output is correct
25 Correct 781 ms 227988 KB Output is correct
26 Correct 792 ms 230472 KB Output is correct
27 Correct 765 ms 230472 KB Output is correct
28 Correct 707 ms 227912 KB Output is correct
29 Correct 740 ms 228044 KB Output is correct
30 Correct 768 ms 227924 KB Output is correct