oj.uz

답안 #1109041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109041 2024-11-05T21:32:25 Z Ludissey 벽 (IOI14_wall) C++14
61 / 100
 787 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){
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 9 ms 1872 KB Output is correct
5 Correct 6 ms 1872 KB Output is correct
6 Correct 5 ms 1992 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 86 ms 19912 KB Output is correct
3 Correct 169 ms 11396 KB Output is correct
4 Correct 498 ms 38216 KB Output is correct
5 Correct 187 ms 34896 KB Output is correct
6 Correct 172 ms 33564 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 8 ms 1872 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Correct 5 ms 1872 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 85 ms 21640 KB Output is correct
9 Correct 158 ms 13384 KB Output is correct
10 Correct 516 ms 38176 KB Output is correct
11 Correct 202 ms 33608 KB Output is correct
12 Correct 191 ms 33620 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 93 ms 19784 KB Output is correct
15 Correct 41 ms 4424 KB Output is correct
16 Correct 787 ms 33552 KB Output is correct
17 Correct 206 ms 33352 KB Output is correct
18 Correct 206 ms 38224 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 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 2040 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 100 ms 19884 KB Output is correct
9 Correct 178 ms 12872 KB Output is correct
10 Correct 551 ms 35660 KB Output is correct
11 Correct 196 ms 33608 KB Output is correct
12 Correct 191 ms 33620 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 98 ms 23072 KB Output is correct
15 Correct 53 ms 4320 KB Output is correct
16 Correct 756 ms 38748 KB Output is correct
17 Correct 206 ms 38216 KB Output is correct
18 Correct 193 ms 33352 KB Output is correct
19 Runtime error 315 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -