oj.uz

Submission #69386

# Submission time Handle Problem Language Result Execution time Memory
69386 2018-08-20T17:36:37 Z MANcity Wall (IOI14_wall) C++14
61 / 100
 1411 ms 263168 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[4*500002];
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 95 ms 94328 KB Output is correct
2 Correct 96 ms 95028 KB Output is correct
3 Correct 87 ms 95028 KB Output is correct
4 Correct 99 ms 95460 KB Output is correct
5 Correct 94 ms 95460 KB Output is correct
6 Correct 92 ms 95612 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 95612 KB Output is correct
2 Correct 579 ms 135268 KB Output is correct
3 Correct 526 ms 135268 KB Output is correct
4 Correct 1335 ms 153680 KB Output is correct
5 Correct 739 ms 162152 KB Output is correct
6 Correct 755 ms 169968 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 169968 KB Output is correct
2 Correct 93 ms 169968 KB Output is correct
3 Correct 91 ms 169968 KB Output is correct
4 Correct 92 ms 169968 KB Output is correct
5 Correct 89 ms 169968 KB Output is correct
6 Correct 99 ms 169968 KB Output is correct
7 Correct 82 ms 169968 KB Output is correct
8 Correct 621 ms 169968 KB Output is correct
9 Correct 610 ms 169968 KB Output is correct
10 Correct 1411 ms 192040 KB Output is correct
11 Correct 749 ms 200512 KB Output is correct
12 Correct 732 ms 208236 KB Output is correct
13 Correct 88 ms 208236 KB Output is correct
14 Correct 704 ms 208236 KB Output is correct
15 Correct 142 ms 208236 KB Output is correct
16 Correct 1291 ms 226996 KB Output is correct
17 Correct 696 ms 233044 KB Output is correct
18 Correct 693 ms 241484 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 241484 KB Output is correct
2 Correct 95 ms 241484 KB Output is correct
3 Correct 88 ms 241484 KB Output is correct
4 Correct 89 ms 241484 KB Output is correct
5 Correct 90 ms 241484 KB Output is correct
6 Correct 93 ms 241484 KB Output is correct
7 Correct 85 ms 241484 KB Output is correct
8 Correct 649 ms 242280 KB Output is correct
9 Correct 498 ms 242280 KB Output is correct
10 Runtime error 1357 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
11 Halted 0 ms 0 KB -