oj.uz

Submission #930216

# Submission time Handle Problem Language Result Execution time Memory
930216 2024-02-19T04:41:53 Z VinhLuu Painting Walls (APIO20_paint) C++17
0 / 100
 3 ms 4716 KB 
#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const int oo = 1e9;
const int mod = 998244353; // 1e9 + 7;
const int M = 5e5 + 5;

bool g[N];
int st[N << 1], f[2][N], dp[N];
vector<int> p[N];

void update(int i,int x, int n){
    i += n - 1;
    st[i] = x;
    while(i > 1){
        i /= 2;
        st[i] = min(st[i << 1], st[i << 1|1]);
    }
}

int get(int l,int r,int n){
    r++;
    int ret= oo;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
        if(l & 1) ret = min(ret, st[l++]);
        if(r & 1) ret = min(ret, st[--r]);
    }
    return ret;
}

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){
    for(int i = 0; i < m; i ++) for(auto j : B[i]) p[j].pb(i);
    memset(f, -1, sizeof(f));
    memset(dp, -1, sizeof(dp));

    for(int i = 1; i <= 2 * n; i ++) st[i] = oo;

    int pre = 0, nx = 1;

    bool afk = false;

    for(int i = n; i >= 1; i --){
        for(auto j : p[C[i - 1]]){
            if(f[pre][(j + 1) % m] == -1) f[nx][j] = i;
            else f[nx][j] = f[pre][(j + 1) % m];
//            if(i == 6) cout << j << " " << (j + 1) % m << " " <<  f[pre][(j + 1) % m] << " k\n";
            if(f[nx][j] - i + 1 >= m) g[i] = true;
        }

        if(i < n) for(auto j : p[C[i]]) f[pre][j] = -1;
//        cout << i << "check\n";
        for(auto j : p[C[i - 1]]){
            f[pre][j] = f[nx][j];
//            cout << j << " " << f[nx][j] << " f\n";
            f[nx][j] = -1;
        }

//        cout << i << " o\n";
//        for(int j = 0; j < m; j ++) cout << j << " " << f[pre][j] << "ff\n";
//        cout << i << " " << g[i] << " g\n";
        if(g[i] == true){

            if(!afk) dp[i] = 1;
            else dp[i] = get(i + 1, i + m, n) + 1;
            update(i, dp[i], n);
//        cout << "fffffffffffffffffffffffff " << i << " " << dp[i] << " \n";
            afk = true;
        }
    }

//    if(dp[1] >= (int)1e9) return -1;
//    else
        return dp[1];
}

//#define LOCAL

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

     int n, m, k; cin >> n >> m >> k;
  vector<int> C, A;
  vector<vector<int>> B;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x;
    C.push_back(x);
  }
  for (int i = 1; i <= m; ++i) {
    int a; cin >> a; A.push_back(a);
    vector<int> vt;
    for (int j = 1; j <= a; ++j) {
      int x; cin >> x;
      vt.push_back(x);
    }
    sort(vt.begin(), vt.end());
    B.push_back(vt);

  }
  cout << minimumInstructions(n, m, k, C, A, B);
}
#endif // LOCAL

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 1 ms 4716 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 1 ms 4716 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 1 ms 4716 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 1 ms 4716 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 1 ms 4716 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -