oj.uz

Submission #980330

# Submission time Handle Problem Language Result Execution time Memory
980330 2024-05-12T05:08:11 Z 8pete8 Painting Walls (APIO20_paint) C++17
0 / 100
 2 ms 7512 KB 
#include "paint.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
/*
sum of f(k)^2 is 4e5
max f(k)is 633????
we can do nf(k)
*/
const int mxn=2e5,mod=1e9+7,inf=1e9;
vector<pii>go[mxn+10];//for each col
int ans[mxn+10],mn[mxn+10];//ans=endpoint of using i
int dp[mxn+10];
int32_t minimumInstructions(int32_t n, int32_t m, int32_t k,vector<int32_t>c,vector<int32_t> A,vector<vector<int32_t>>B){
  for(int i=0;i<m;i++)for(auto j:B[i])go[j].pb({i,0});
  int cur=0;
  stack<pii>st;
  st.push({-1,0});
  auto get=[&](int x){//will this work?
    pii a;
    while(!st.empty()&&st.top().f>=x)a=st.top(),st.pop();
    st.push(a);
    return a.s;
  };
  for(int i=0;i<=k;i++)mn[i]=inf;
  ans[0]=-1;
  for(int i=0;i<n;i++){
    for(auto &j:go[c[i]]){
      if(mn[j.f]!=inf)j.s=mn[j.f];
      else j.s=i;//start here
      if(i-j.s+1>=m){
        int x=get(i-m);
        if(x==inf)continue;
        ans[x+1]=i;
        st.push({i,x+1});
        cur=x+1;
      }
    }
    if(i)for(auto j:go[c[i-1]])mn[(j.f+1)%m]=inf;//clear
    for(auto j:go[c[i]])mn[(j.f+1)%m]=min(mn[(j.f+1)%m],j.s);//nxt start
  }
  if(ans[cur]<n-1)return -1;
  return cur;
}

/*
int32_t main(){
  int n,m,k;cin>>n>>m>>k;
  vector<int>c(n),a(m);
  vector<vector<int>>b(m);
  for(int i=0;i<n;i++)cin>>c[i];
  for(int i=0;i<m;i++){
    cin>>a[i];
    for(int j=0;j<a[i];j++){
      int x;cin>>x;
      b[i].pb(x);
    }
  }
  cout<<minimumInstructions(n,m,k,c,a,b);
}*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7296 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7296 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7296 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7296 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7296 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -