oj.uz

Submission #900303

# Submission time Handle Problem Language Result Execution time Memory
900303 2024-01-08T05:18:44 Z 12345678 Seats (IOI18_seats) C++17
0 / 100
 170 ms 36176 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
int N, v[nx], l[nx];

struct segtree
{
    struct node
    {
        int mn, f, lz;
    } d[4*nx];
    node merge(node a, node b)
    {
        if (a.mn==b.mn) a.f+=b.f;
        if (a.mn<=b.mn) return a;
        else return b;
    }
    void pushlz(int l, int r, int i)
    {
        if (l==r) return d[i].mn+=d[i].lz, d[i].lz=0, void();
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].mn+=d[i].lz;
        d[i].lz=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i].f=1);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
} s;

void updateseats(int idx, int mul)
{
    if (idx==0||idx==N+1) return;
    int c=(v[idx+1]>v[idx])?1:-1;
    c+=(v[idx-1]>v[idx])?1:-1;
    s.update(1, N, 1, v[idx], N, mul*c);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    N=W;
    for (int i=1; i<=N; i++) l[i]=C[i-1]+1;
    for (int i=1; i<=N; i++) v[l[i]]=i;
    v[0]=v[N+1]=1e9;
    s.build(1, N, 1);
    for (int i=1; i<=N; i++) updateseats(l[i], 1);
}

int swap_seats(int a, int b) {
    a++; b++;
    for (int i=-1; i<=1; i++) updateseats(l[a]+i, -1), updateseats(l[b]+i, -1);
    swap(v[l[a]], v[l[b]]);
    swap(l[a], l[b]);
    /*
    cout<<"update \n";
    for (int i=1; i<=N; i++) cout<<l[i]<<' ';
    cout<<'\n';
    for (int i=1; i<=N; i++) cout<<v[i]<<' ';
    cout<<'\n';*/
    for (int i=-1; i<=1; i++) updateseats(l[a]+i, 1), updateseats(l[b]+i, 1);
    return s.d[1].f;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 30.0

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