oj.uz

답안 #250674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250674 2020-07-18T16:50:18 Z uacoder123 벽 (IOI14_wall) C++14
61 / 100
 1492 ms 262148 KB 
#include <stdio.h>
#include "wall.h"
#include <stdlib.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;

ii segt[8000001],lazy[8000001];
ii imp(ii o,ii n)
{
  if(o==mp(8000001*1LL,0*1LL))
    return(n);
  else if(n==mp(8000001*1LL,0*1LL))
    return(o);
  if(o.S<=n.F)
    return(mp(n.F,n.F));
  if(o.S>=n.F&&o.F<=n.F&&n.S>=o.S)
    return(mp(n.F,o.S));
  if(n.F>=o.F&&n.S<=o.S)
    return(n);
  if(o.F>=n.F&&o.S<=n.S)
    return(o);
  if(o.F>=n.F&&o.S>=n.S&&n.S>=o.F)
    return(mp(o.F,n.S));
  if(o.F>=n.S)
    return(mp(n.S,n.S));
}
void up(int node,int l,int r,int t,int s,int e,int h)
{
  if(lazy[node]!=mp(8000001*1LL,0*1LL))
  {
    segt[node]=imp(segt[node],lazy[node]);
    lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
    lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
    lazy[node]=mp(8000001*1LL,0*1LL);
  }
  if(l>e||r<s)
    return;
  if(l>=s&&r<=e)
  {
    segt[node]=imp(segt[node],(t==1)?(mp(h,1000000)):(mp(0,h)));
    lazy[2*node+1]=imp(lazy[2*node+1],(t==1)?(mp(h,1000000)):(mp(0,h)));
    lazy[2*node+2]=imp(lazy[2*node+2],(t==1)?(mp(h,1000000)):(mp(0,h)));
    return;
  }
  int m=(l+r)/2;
  up(2*node+1,l,m,t,s,e,h);
  up(2*node+2,m+1,r,t,s,e,h);
  segt[node]=mp(min(segt[2*node+1].F,segt[2*node+2].F),max(segt[2*node+1].S,segt[2*node+2].S));
}
ii qu(int node,int l,int r,int s,int e)
{
if(lazy[node]!=mp(8000001*1LL,0*1LL))
  {
    segt[node]=imp(segt[node],lazy[node]);
    lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
    lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
    lazy[node]=mp(8000001,0);
  }
  if(l>e||r<s)
    return(mp(8000001,0));
  if(l>=s&&r<=e)
  {
    return(segt[node]);
  }
  int m=(l+r)/2;
  ii q1=qu(2*node+1,l,m,s,e),q2=qu(2*node+2,m+1,r,s,e);
  return(mp(min(q1.F,q2.F),max(q1.S,q2.S)));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  for(int i=0;i<8000001;++i)
  {
    lazy[i]=mp(8000001,0);
    segt[i]=mp(8000001,0);
  }
  for(int i=0;i<k;++i)
  {
    up(0,0,n-1,op[i],left[i],right[i],height[i]);
  }
  for(int i=0;i<n;++i)
  {
    finalHeight[i]=(qu(0,0,n-1,i,i)).F;
    if(finalHeight[i]==8000001)
      finalHeight[i]=0;
  }
  return;
}

Compilation message

wall.cpp: In function 'ii imp(ii, ii)':
wall.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 250744 KB Output is correct
2 Correct 118 ms 250872 KB Output is correct
3 Correct 117 ms 250896 KB Output is correct
4 Correct 126 ms 251128 KB Output is correct
5 Correct 122 ms 251000 KB Output is correct
6 Correct 123 ms 251000 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 250744 KB Output is correct
2 Correct 302 ms 262144 KB Output is correct
3 Correct 499 ms 258040 KB Output is correct
4 Correct 1492 ms 262144 KB Output is correct
5 Correct 517 ms 262144 KB Output is correct
6 Correct 484 ms 262144 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 250872 KB Output is correct
2 Correct 116 ms 250876 KB Output is correct
3 Correct 111 ms 250872 KB Output is correct
4 Correct 122 ms 251128 KB Output is correct
5 Correct 123 ms 251128 KB Output is correct
6 Correct 123 ms 251128 KB Output is correct
7 Correct 112 ms 250744 KB Output is correct
8 Correct 297 ms 262144 KB Output is correct
9 Correct 482 ms 258040 KB Output is correct
10 Correct 1361 ms 262144 KB Output is correct
11 Correct 498 ms 262144 KB Output is correct
12 Correct 493 ms 262144 KB Output is correct
13 Correct 116 ms 250744 KB Output is correct
14 Correct 305 ms 262144 KB Output is correct
15 Correct 175 ms 252024 KB Output is correct
16 Correct 1420 ms 262144 KB Output is correct
17 Correct 508 ms 262144 KB Output is correct
18 Correct 507 ms 262144 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 250872 KB Output is correct
2 Correct 120 ms 250876 KB Output is correct
3 Correct 131 ms 250864 KB Output is correct
4 Correct 131 ms 251004 KB Output is correct
5 Correct 130 ms 251000 KB Output is correct
6 Correct 130 ms 251128 KB Output is correct
7 Correct 121 ms 250744 KB Output is correct
8 Correct 311 ms 262144 KB Output is correct
9 Correct 509 ms 258040 KB Output is correct
10 Correct 1332 ms 262144 KB Output is correct
11 Correct 510 ms 262144 KB Output is correct
12 Correct 494 ms 262144 KB Output is correct
13 Correct 122 ms 250908 KB Output is correct
14 Correct 336 ms 262144 KB Output is correct
15 Correct 231 ms 252024 KB Output is correct
16 Correct 1422 ms 262144 KB Output is correct
17 Correct 502 ms 262144 KB Output is correct
18 Correct 494 ms 262144 KB Output is correct
19 Runtime error 1020 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -