Submission #800840

#	Time	Username	Problem	Language	Result	Execution time	Memory
800840		Liudas	Wall (IOI14_wall)	C++17	32 / 100	455 ms	30352 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int fh[]){
    if(N <= 10000 && K <= 5000){
        for(int i = 0; i < K; i ++){
            for(int j = l[i]; j < r[i] + 1; j ++){
                if(op[i] == 1){
                    fh[j] = max(h[i], fh[j]);
                }
                else{
                    fh[j] = min(h[i], fh[j]);
                }
            }
        }
    }
    else{
        vector<vector<int>> arr(N + 5);
        for(int i = 0; i < K; i ++){
            if(op[i] == 2)continue;
            arr[l[i]].push_back(h[i] + 1);
            arr[r[i]+1].push_back(-h[i] - 1);
        }
        multiset<int> mov;
        mov.insert(0);
        for(int i = 0; i < N; i ++){
            for(int j : arr[i]){
                if(j > 0)
                mov.insert(j-1);
                else
                mov.erase(mov.find(-j - 1));
            }
            fh[i] = *mov.rbegin();
            arr[i].clear();
        }
        mov.clear();
        for(int i = 0; i < K; i ++){
            if(op[i] == 1)continue;
            arr[l[i]].push_back(h[i] + 1);
            arr[r[i]+1].push_back(-h[i] - 1);
        }
        mov.insert(1e9);
        for(int i = 0; i < N; i ++){
            for(int j : arr[i]){
                if(j > 0)
                mov.insert(j-1);
                else
                mov.erase(mov.find(-j - 1));
            }
            fh[i] = min(fh[i], *mov.begin());
            arr[i].clear();
        }
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39