oj.uz

Submission #69390

# Submission time Handle Problem Language Result Execution time Memory
69390 2018-08-20T17:44:31 Z MANcity Wall (IOI14_wall) C++14
100 / 100
 1404 ms 243332 KB 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "wall.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
struct vert
{
    int after_op;
    int do_0;
    int do_109;
    int ma;
    int mi;
}t[2*1000002];
int give_value(int x,vert V)
{
    if(V.ma>=x)
        return V.do_0;
    if(V.mi<=x)
        return V.do_109;
    return x;
}
vert combine(vert V1,vert V2)
{
    vert V;
    V.after_op=give_value(V1.after_op,V2);
    V.do_0=give_value(V1.do_0,V2);
    V.do_109=give_value(V1.do_109,V2);
    V.ma=max(V1.ma,V2.ma);
    V.mi=min(V1.mi,V2.mi);
    return V;
}
int U=0;
void update(int left,int right,int pos,int v,pair<int,int> val)
{
    if(left==right)
    {
        if(val.first==0)
        {
            t[v].after_op=0;
            t[v].do_0=0;
            t[v].do_109=val.second;
            t[v].mi=val.second;
            t[v].ma=0;
        }
        if(val.first==1)
        {
            t[v].after_op=val.second;
            t[v].do_0=val.second;
            t[v].do_109=100000000;
            t[v].ma=val.second;
            t[v].mi=100000000;
        }
    }
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update(left,m,pos,2*v,val);
        else
            update(m+1,right,pos,2*v+1,val);
        t[v]=combine(t[2*v],t[2*v+1]);
    }
}
vector<pair<int,pair<int,int> > > aj[2000002];
vector<pair<int,pair<int,int> > > dzax[2000002];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for0(i,k-1)
    {
        aj[left[i]].pb({i,{height[i],2-op[i]}});
        dzax[right[i]].pb({i,{10000000,0}});
    }
    for0(i,k-1)
        update(0,k-1,i,1,{0,100000000});
    for0(i,n-1)
    {
        for0(j,aj[i].size()-1)
        {
            int H=aj[i][j].second.first;
            int POS=aj[i][j].first;
            int OP=aj[i][j].second.second;
            update(0,k-1,POS,1,{OP,H});
        }
        finalHeight[i]=t[1].after_op;
        for0(j,dzax[i].size()-1)
        {
            int H=dzax[i][j].second.first;
            int POS=dzax[i][j].first;
            int OP=dzax[i][j].second.second;
            update(0,k-1,POS,1,{OP,H});
        }
    }
    return ;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
/*
4 1
1 0 0 5
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 94200 KB Output is correct
2 Correct 98 ms 94952 KB Output is correct
3 Correct 89 ms 94952 KB Output is correct
4 Correct 96 ms 95424 KB Output is correct
5 Correct 97 ms 95424 KB Output is correct
6 Correct 110 ms 95564 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 95564 KB Output is correct
2 Correct 607 ms 135188 KB Output is correct
3 Correct 555 ms 135188 KB Output is correct
4 Correct 1404 ms 144896 KB Output is correct
5 Correct 723 ms 144896 KB Output is correct
6 Correct 705 ms 144896 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 144896 KB Output is correct
2 Correct 100 ms 144896 KB Output is correct
3 Correct 94 ms 144896 KB Output is correct
4 Correct 95 ms 144896 KB Output is correct
5 Correct 90 ms 144896 KB Output is correct
6 Correct 94 ms 144896 KB Output is correct
7 Correct 92 ms 144896 KB Output is correct
8 Correct 597 ms 144896 KB Output is correct
9 Correct 533 ms 144896 KB Output is correct
10 Correct 1285 ms 144896 KB Output is correct
11 Correct 810 ms 144896 KB Output is correct
12 Correct 721 ms 144896 KB Output is correct
13 Correct 87 ms 144896 KB Output is correct
14 Correct 724 ms 144896 KB Output is correct
15 Correct 162 ms 144896 KB Output is correct
16 Correct 1388 ms 145136 KB Output is correct
17 Correct 689 ms 145136 KB Output is correct
18 Correct 767 ms 145136 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 145136 KB Output is correct
2 Correct 94 ms 145136 KB Output is correct
3 Correct 92 ms 145136 KB Output is correct
4 Correct 93 ms 145136 KB Output is correct
5 Correct 93 ms 145136 KB Output is correct
6 Correct 97 ms 145136 KB Output is correct
7 Correct 83 ms 145136 KB Output is correct
8 Correct 597 ms 145136 KB Output is correct
9 Correct 496 ms 145136 KB Output is correct
10 Correct 1361 ms 145136 KB Output is correct
11 Correct 756 ms 148644 KB Output is correct
12 Correct 820 ms 148644 KB Output is correct
13 Correct 88 ms 148644 KB Output is correct
14 Correct 628 ms 148644 KB Output is correct
15 Correct 145 ms 148644 KB Output is correct
16 Correct 1362 ms 150584 KB Output is correct
17 Correct 743 ms 150584 KB Output is correct
18 Correct 683 ms 150584 KB Output is correct
19 Correct 999 ms 172464 KB Output is correct
20 Correct 1294 ms 172464 KB Output is correct
21 Correct 1027 ms 172576 KB Output is correct
22 Correct 960 ms 172576 KB Output is correct
23 Correct 1118 ms 172576 KB Output is correct
24 Correct 1057 ms 180732 KB Output is correct
25 Correct 1006 ms 190972 KB Output is correct
26 Correct 1066 ms 203992 KB Output is correct
27 Correct 948 ms 214548 KB Output is correct
28 Correct 899 ms 222464 KB Output is correct
29 Correct 1002 ms 232924 KB Output is correct
30 Correct 915 ms 243332 KB Output is correct