oj.uz

Submission #93530

# Submission time Handle Problem Language Result Execution time Memory
93530 2019-01-09T11:37:22 Z Bodo171 Wall (IOI14_wall) C++14
100 / 100
 1934 ms 136816 KB 
#include "wall.h"
#include <iostream>
#include <climits>
#include <set>
using namespace std;
const int nmax=2*1000*1000+5;
struct aint
{
    int mn,mx,whmn,whmx;
}arb[4*nmax],ans;
void mrg(aint &A,aint B,aint C)
{
    A=B;
    if(C.mn<A.mn) A.mn=C.mn,A.whmn=C.whmn;
    if(C.mx>A.mx) A.mx=C.mx,A.whmx=C.whmx;
}
set<int> s;
set<int>::iterator it,it1;
int v[nmax];
int n,poz,i;
void upd(int nod,int l,int r,int poz)
{
    if(l==r)
    {
        arb[nod].mx=arb[nod].mn=v[poz];
        arb[nod].whmx=arb[nod].whmn=poz;
        if(v[poz]==-1)
        {
            arb[nod].mx=-1;arb[nod].mn=INT_MAX;
        }
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) upd(2*nod,l,m,poz);
    else upd(2*nod+1,m+1,r,poz);
    mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        mrg(ans,ans,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m,st,dr);
    if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int getmx(int st,int dr)
{
    ans.mx=-1,ans.mn=INT_MAX;
    query(1,1,n,st,dr);
    poz=ans.whmx;
    return ans.mx;
}
int getmn(int st,int dr)
{
    ans.mx=-1,ans.mn=INT_MAX;
    query(1,1,n,st,dr);
    poz=ans.whmn;
    return ans.mn;
}
void rs(int wh,int llim,int H)
{
    it=s.lower_bound(wh);
    if(it!=s.begin())
    {
        it--;
        if((*it)<llim-1)
        {
            v[llim-1]=v[wh];
            s.insert(llim-1);
            upd(1,1,n,llim-1);
        }
    }
    else
    {
        if(llim-1)
        {
            v[llim-1]=v[wh];
            s.insert(llim-1);
            upd(1,1,n,llim-1);
        }
    }
    s.insert(wh);
    v[wh]=H;
    upd(1,1,n,wh);
}
void comp(int poz)
{
    it=s.lower_bound(poz);
    bool brk=0;
    if(it!=s.begin())
    {
        it--;
        while(it!=s.begin()&&(!brk))
        {
            if(v[(*it)]!=v[poz]) brk=1;
            else
            {
                v[(*it)]=-1;
                upd(1,1,n,(*it));
                it1=it;
                it1--;
                s.erase(it);
                it=it1;
            }
        }
    }
    if(s.upper_bound(poz)!=s.end()&&v[(*s.upper_bound(poz))]==v[poz])
    {
        v[poz]=-1;upd(1,1,n,poz);
        s.erase(poz);
    }
}
bool finds(int x)
{
    return (s.find(x)!=s.end());
}
void build(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod].whmx=arb[nod].whmn=l;
        arb[nod].mx=-1;arb[nod].mn=INT_MAX;
        return;
    }
    int m=(l+r)/2;
    build(2*nod,l,m);
    build(2*nod+1,m+1,r);
    mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n=N;
  build(1,1,n);
  int h,pp;
  s.insert(n);
  v[n]=0;
  upd(1,1,n,n);
  for(int i=0;i<k;i++)
  {
      left[i]++;right[i]++;
      h=height[i];
      if(op[i]==1)
      {
          while(getmn(left[i],right[i])<h)
          {
              if(finds(poz))
              {
               rs(poz,left[i],h);
               if(finds(left[i]-1))comp(left[i]-1);
               if(finds(poz)) comp(poz);
              }
          }
          pp=(*s.lower_bound(right[i]));
          if(getmn(pp,pp)<h)
          {
              rs(pp,left[i],v[pp]);
              rs(right[i],left[i],h);
              if(finds(left[i]-1))comp(left[i]-1);
              if(finds(right[i])) comp(right[i]);
          }
      }
      else
      {
          while(getmx(left[i],right[i])>h)
          {
              if(finds(poz))
              rs(poz,left[i],h);
          }
          pp=(*s.lower_bound(right[i]));
          if(getmx(pp,pp)>h)
          {
              rs(pp,left[i],v[pp]);
              rs(right[i],left[i],h);
              upd(1,1,n,right[i]);
              if(finds(left[i]-1))comp(left[i]-1);
              if(finds(right[i])) comp(right[i]);
          }
      }
  }
  for(i=1;i<=n;i++)
    if(finds(i)) finalHeight[i-1]=v[i];
  for(i=n-1;i>=0;i--)
    if(!finds(i+1))
      finalHeight[i]=finalHeight[i+1];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 14 ms 1016 KB Output is correct
5 Correct 13 ms 1272 KB Output is correct
6 Correct 21 ms 1272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 141 ms 8104 KB Output is correct
3 Correct 137 ms 4792 KB Output is correct
4 Correct 387 ms 22764 KB Output is correct
5 Correct 233 ms 23500 KB Output is correct
6 Correct 230 ms 22004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 15 ms 1144 KB Output is correct
5 Correct 14 ms 1272 KB Output is correct
6 Correct 14 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 143 ms 8172 KB Output is correct
9 Correct 142 ms 4828 KB Output is correct
10 Correct 454 ms 22808 KB Output is correct
11 Correct 237 ms 23560 KB Output is correct
12 Correct 231 ms 22136 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 158 ms 13920 KB Output is correct
15 Correct 85 ms 2684 KB Output is correct
16 Correct 1538 ms 23156 KB Output is correct
17 Correct 928 ms 24588 KB Output is correct
18 Correct 951 ms 24468 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 15 ms 1016 KB Output is correct
5 Correct 14 ms 1400 KB Output is correct
6 Correct 14 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 144 ms 8312 KB Output is correct
9 Correct 140 ms 4856 KB Output is correct
10 Correct 385 ms 22780 KB Output is correct
11 Correct 235 ms 23544 KB Output is correct
12 Correct 230 ms 22012 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 160 ms 13980 KB Output is correct
15 Correct 81 ms 2684 KB Output is correct
16 Correct 1533 ms 23292 KB Output is correct
17 Correct 928 ms 24584 KB Output is correct
18 Correct 925 ms 24576 KB Output is correct
19 Correct 1905 ms 136732 KB Output is correct
20 Correct 1827 ms 134352 KB Output is correct
21 Correct 1934 ms 136752 KB Output is correct
22 Correct 1907 ms 134436 KB Output is correct
23 Correct 1898 ms 134336 KB Output is correct
24 Correct 1852 ms 134300 KB Output is correct
25 Correct 1876 ms 134448 KB Output is correct
26 Correct 1906 ms 136816 KB Output is correct
27 Correct 1908 ms 136796 KB Output is correct
28 Correct 1888 ms 134288 KB Output is correct
29 Correct 1898 ms 134340 KB Output is correct
30 Correct 1887 ms 134404 KB Output is correct