oj.uz

답안 #745378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745378 2023-05-19T22:53:59 Z Lobo 벽 칠하기 (APIO20_paint) C++17
0 / 100
 0 ms 212 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 1e9+10;

int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
    vector<int> f[k];
    for(int i = 0; i < m; i++) {
        sort(all(b[i]));
        for(auto x : b[i]) {
            f[x].pb(i);
        }
    }

    vector<pair<int,int>> pos;
    for(int i = n-1; i >= 0; i-= m) {
        for(auto j : f[c[i]]) {
            int cnt;
            int li = i;
            int lj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(li < 0 || b[lj].back() < c[li] || *lower_bound(all(b[lj]),c[li]) != c[li]) {
                    li++;
                    break;
                }
                li--;
                lj--;
                lj = (lj%m+m)%m;
            }

            int ri = i;
            int rj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(ri > n-1 || b[rj].back() < c[ri] || *lower_bound(all(b[rj]),c[ri]) != c[ri]) {
                    ri--;
                    break;
                }
                ri++;
                rj++;
                rj = (rj%m+m)%m;
            }
            pos.pb(mp(li,ri));
            // cout << i << " " << j << " " << li << " " << ri << endl;
        }
    }

    sort(all(pos));

    vector<pair<int,int>> pos1;
    for(auto X : pos) {
        while(pos1.size() && pos1.back().fr == X.fr) pos1.pop_back();
        if(pos1.size() && pos1.back().sc >= X.sc) continue;
        pos1.pb(X);
    }
    swap(pos,pos1);
    reverse(all(pos));
    for(auto x : pos) {
        // cout << x.fr << " " << x.sc << endl;
    }
    vector<int> dp(n+1,inf);
    dp[0] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push(mp(0,0));
    pq.push(mp(-inf,n));
    for(int i = 0; i <= n; i++) {
        while(pq.top().sc < i) pq.pop();
        dp[i] = pq.top().fr;
        if(dp[i] == inf) continue;
        while(pos.size() && pos.back().sc < i+m-1) pos.pop_back();
        if(pos.empty() || pos.back().fr > i) continue;
        // cout << i << "   " << dp[i] << " " << i+m << endl;
        pq.push(mp(-(dp[i]+1),i+m));
        // dp[i+m] = dp[i]+1;
        // for(int j = i+1; j <= i+m; j++) {
        //     dp[j] = min(dp[j],dp[i]+1);
        // }
    }

    if(dp[n] == inf) return -1;
    return dp[n];
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:65:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   65 |     for(auto x : pos) {
      |              ^

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -