oj.uz

Submission #1109000

# Submission time Handle Problem Language Result Execution time Memory
1109000 2024-11-05T18:39:33 Z Ludissey Wall (IOI14_wall) C++17
32 / 100
 3000 ms 40576 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;
    bool markedMN=false;
    bool markedMX=false;
    int lazy=0;
    void update(){
      sum=left->sum+right->sum;
    }
};
 
struct segtree {
  int n;
  node* root=new node{nullptr,nullptr,0,false,false,0};
  void propagate(node* x){
    if(x->markedMN){
      if(x->left==NULL){
        x->sum=min(x->sum,x->lazy);
        x->markedMN=false;
        return;
      }
      if(x->left->markedMN){
        x->left->lazy=min(x->left->lazy, x->lazy);
      }else {
        if(x->left->markedMX) propagate(x->left);
        x->left->lazy=x->lazy;
        x->left->markedMN=true;
      }
      if(x->right->markedMN){
        x->right->lazy=min(x->right->lazy, x->lazy);
      }else {
        if(x->right->markedMX) propagate(x->right);
        x->right->lazy=x->lazy;
        x->right->markedMN=true;
      }
      x->markedMN=false;
      x->lazy=0;
    }else if(x->markedMX){
      if(x->left==NULL){
        x->sum=max(x->sum,x->lazy);
        x->markedMX=false;
        return;
      }
      if(x->left->markedMX){
        x->left->lazy=max(x->left->lazy, x->lazy);
      }else {
        if(x->left->markedMN) propagate(x->left);
        x->left->lazy=x->lazy;
        x->left->markedMX=true;
      }
      if(x->right->markedMX){
        x->right->lazy=max(x->right->lazy, x->lazy);
      }else {
        if(x->right->markedMN) propagate(x->right);
        x->right->lazy=x->lazy;
        x->right->markedMX=true;
      }
      x->markedMX=false;
      x->lazy=0;
    }
  }

  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){
      x->lazy=v;
      x->markedMN=true;
      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){
      x->lazy=v;
      x->markedMX=true;
      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,false,false,0};
      x->right=new node{nullptr,nullptr,0,false,false,0};
      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 3 ms 336 KB Output is correct
4 Correct 97 ms 1784 KB Output is correct
5 Correct 116 ms 1616 KB Output is correct
6 Correct 116 ms 1684 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 88 ms 25776 KB Output is correct
3 Correct 179 ms 13936 KB Output is correct
4 Correct 537 ms 39564 KB Output is correct
5 Correct 221 ms 40520 KB Output is correct
6 Correct 229 ms 38984 KB Output is correct

Subtask #3
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 3 ms 336 KB Output is correct
4 Correct 68 ms 1616 KB Output is correct
5 Correct 139 ms 1616 KB Output is correct
6 Correct 141 ms 1616 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 131 ms 25672 KB Output is correct
9 Correct 170 ms 14152 KB Output is correct
10 Correct 540 ms 39484 KB Output is correct
11 Correct 250 ms 40576 KB Output is correct
12 Correct 210 ms 39068 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 112 ms 25592 KB Output is correct
15 Correct 773 ms 3912 KB Output is correct
16 Execution timed out 3056 ms 38964 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.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 3 ms 336 KB Output is correct
4 Correct 91 ms 1688 KB Output is correct
5 Correct 145 ms 1616 KB Output is correct
6 Correct 120 ms 1692 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 145 ms 25600 KB Output is correct
9 Correct 163 ms 14152 KB Output is correct
10 Correct 597 ms 39500 KB Output is correct
11 Correct 199 ms 40536 KB Output is correct
12 Correct 219 ms 38860 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 93 ms 25788 KB Output is correct
15 Correct 787 ms 3912 KB Output is correct
16 Execution timed out 3063 ms 38980 KB Time limit exceeded
17 Halted 0 ms 0 KB -