oj.uz

Submission #875194

# Submission time Handle Problem Language Result Execution time Memory
875194 2023-11-18T18:52:21 Z abcvuitunggio Seats (IOI18_seats) C++17
33 / 100
 451 ms 69536 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct T{
    int mn,cnt,sum;
}st[4000001];
int n;
vector <int> r,c;
vector <vector <int>> a;
T operator +(T a, T b){
    T c;
    c.mn=min(a.mn,a.sum+b.mn);
    if (a.mn==a.sum+b.mn)
        c.cnt=a.cnt+b.cnt;
    else if (a.mn<a.sum+b.mn)
        c.cnt=a.cnt;
    else
        c.cnt=b.cnt;
    c.sum=a.sum+b.sum;
    return c;
}
int cell(int i, int j){
    return (i<0||i>=a.size()||j<0||j>=a[0].size()?n:a[i][j]);
}
pair <int, int> best(int i, int j){
    int x=n,y=n;
    for (int k=0;k<2;k++)
        for (int l=0;l<2;l++){
            int val=cell(i+k,j+l);
            if (val<x){
                y=x;
                x=val;
            }
            else
                y=min(y,val);
        }
    return {x,y};
}
int calc(int i){
    int res=0;
    for (int j=0;j<2;j++)
        for (int k=0;k<2;k++){
            auto [x,y]=best(r[i]-j,c[i]-k);
            res+=(i==x)-(i==y);
        }
    return res;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={calc(l),1,calc(l)};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int i){
    if (l>i||r<i||l>r)
        return;
    if (l==r){
        st[node]={calc(i),1,calc(i)};
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node]=st[node<<1]+st[node<<1|1];
}
void give_initial_chart(int H, int W, vector <int> R, vector <int> C){
    r=R;
    c=C;
    n=H*W;
    a.resize(H);
    for (int i=0;i<H;i++)
        a[i].assign(W,0);
    for (int i=0;i<n;i++)
        a[r[i]][c[i]]=i;
    build(1,0,n-1);
}
int swap_seats(int x, int y){
    swap(r[x],r[y]);
    swap(c[x],c[y]);
    swap(a[r[x]][c[x]],a[r[y]][c[y]]);
    for (int i=-1;i<2;i++){
        update(1,0,n-1,cell(r[x]+i,c[x]));
        update(1,0,n-1,cell(r[x],c[x]+i));
        update(1,0,n-1,cell(r[y]+i,c[y]));
        update(1,0,n-1,cell(r[y],c[y]+i));
    }
    return st[1].cnt;
}

Compilation message

seats.cpp: In function 'int cell(int, int)':
seats.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     return (i<0||i>=a.size()||j<0||j>=a[0].size()?n:a[i][j]);
      |                  ~^~~~~~~~~~
seats.cpp:23:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     return (i<0||i>=a.size()||j<0||j>=a[0].size()?n:a[i][j]);
      |                                    ~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3160 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 39 ms 1996 KB Output is correct
2 Correct 58 ms 1996 KB Output is correct
3 Correct 72 ms 2000 KB Output is correct
4 Correct 95 ms 2128 KB Output is correct
5 Correct 118 ms 4556 KB Output is correct
6 Correct 418 ms 69432 KB Output is correct
7 Correct 427 ms 69440 KB Output is correct
8 Correct 443 ms 69536 KB Output is correct
9 Correct 451 ms 69456 KB Output is correct
10 Correct 351 ms 69464 KB Output is correct
11 Correct 368 ms 69440 KB Output is correct
12 Correct 355 ms 69436 KB Output is correct

Subtask #6
0 / 30.0

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