oj.uz

Submission #205404

# Submission time Handle Problem Language Result Execution time Memory
205404 2020-02-28T20:07:41 Z oko Wall (IOI14_wall) C++14
24 / 100
 1132 ms 38612 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >mx[100005],mn[100005];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<k;i++)
    {
        int l=left[i],r=right[i],h=height[i];
        if(op[i]==1)
        {
            mx[l].push_back({0,h});
            mx[r+1].push_back({1,h});
        }
        else
        {
            mn[l].push_back({0,h});
            mn[r+1].push_back({1,h});
        }
    }
    multiset<int>ms;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<mx[i].size();j++)
        {
            pair<int,int>x=mx[i][j];
            if(x.first==0)ms.insert(x.second);
            else ms.erase(ms.lower_bound(x.second));
        }
        if(ms.size()==0)continue;
        finalHeight[i]=*--ms.end();
    }
    ms.clear();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<mn[i].size();j++)
        {
            pair<int,int>x=mn[i][j];
            if(x.first==0)ms.insert(x.second);
            else ms.erase(ms.lower_bound(x.second));
        }
        if(ms.size()==0)continue;
        int z=*ms.begin();
        finalHeight[i]=min(finalHeight[i],z);
    }
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<mx[i].size();j++)
                     ~^~~~~~~~~~~~~
wall.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<mn[i].size();j++)
                     ~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Incorrect 11 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 682 ms 38612 KB Output is correct
3 Correct 305 ms 18040 KB Output is correct
4 Correct 1132 ms 36896 KB Output is correct
5 Correct 307 ms 27256 KB Output is correct
6 Correct 305 ms 27432 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4988 KB Output is correct
2 Incorrect 10 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 12 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -