oj.uz

Submission #900310

# Submission time Handle Problem Language Result Execution time Memory
900310 2024-01-08T05:39:24 Z 12345678 Seats (IOI18_seats) C++17
33 / 100
 665 ms 67404 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++;
    set<int> tmp;
    for (int i=-1; i<=1; i++) tmp.insert(l[a]+i), tmp.insert(l[b]+i);
    for (auto x:tmp) updateseats(x, -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 (auto x:tmp) updateseats(x, 1);
    return s.d[1].f;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 20056 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 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5592 KB Output is correct
2 Correct 46 ms 6132 KB Output is correct
3 Correct 76 ms 6096 KB Output is correct
4 Correct 106 ms 6276 KB Output is correct
5 Correct 140 ms 8576 KB Output is correct
6 Correct 625 ms 67404 KB Output is correct
7 Correct 647 ms 67152 KB Output is correct
8 Correct 590 ms 67396 KB Output is correct
9 Correct 665 ms 67348 KB Output is correct
10 Correct 621 ms 67356 KB Output is correct
11 Correct 605 ms 67140 KB Output is correct
12 Correct 579 ms 67352 KB Output is correct

Subtask #6
0 / 30.0

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