oj.uz

Submission #446836

# Submission time Handle Problem Language Result Execution time Memory
446836 2021-07-23T12:19:48 Z MOUF_MAHMALAT Paint (COI20_paint) C++11
9 / 100
 72 ms 6564 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,m,a[200009],p[200009];
ll l[200009],r[200009],q;
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y||a[x]!=a[y])
        return;
    if(r[x]-l[x]<r[y]-l[y])
        swap(x,y);
    p[y]=x;
    l[x]=min(l[x],l[y]);
    r[x]=max(r[x],r[y]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(ll i=1; i<=m; i++)
    {
        cin>>a[i];
        p[i]=l[i]=r[i]=i;
    }
    for(ll i=1; i<m; i++)
        mrg(i,i+1);
    cin>>q;
    while(q--)
    {
        ll x,y;
        cin>>x>>x>>y;
        x=gp(x);
        a[x]=y;
        if(l[x]>1)
            mrg(x,l[x]-1);
        if(r[x]<m)
            mrg(x,r[x]+1);
    }
    for(ll i=1; i<=m; i++)
        cout<<a[gp(i)]<<" ";
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1112 KB Output is correct
2 Correct 53 ms 3224 KB Output is correct
3 Correct 72 ms 6564 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -