oj.uz

Submission #875196

# Submission time Handle Problem Language Result Execution time Memory
875196 2023-11-18T18:55:06 Z abcvuitunggio Seats (IOI18_seats) C++17
33 / 100
 1471 ms 53396 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]);
}
vector <int> best(int i, int j){
    vector <int> v;
    for (int k=0;k<2;k++)
        for (int l=0;l<2;l++)
            v.push_back(cell(i+k,j+l));
    sort(v.begin(),v.end());
    return v;
}
int calc(int i){
    int res=0;
    for (int j=0;j<2;j++)
        for (int k=0;k<2;k++){
            auto v=best(r[i]-j,c[i]-k);
            res+=(i==v[0])-(i==v[1])+(i==v[2])-(i==v[3]);
        }
    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 48 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 2908 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 293 ms 1484 KB Output is correct
2 Correct 341 ms 1360 KB Output is correct
3 Correct 360 ms 1484 KB Output is correct
4 Correct 413 ms 1516 KB Output is correct
5 Correct 427 ms 3848 KB Output is correct
6 Correct 1410 ms 53276 KB Output is correct
7 Correct 1406 ms 53032 KB Output is correct
8 Correct 1363 ms 53272 KB Output is correct
9 Correct 1471 ms 53364 KB Output is correct
10 Correct 1396 ms 53072 KB Output is correct
11 Correct 1398 ms 53208 KB Output is correct
12 Correct 1318 ms 53396 KB Output is correct

Subtask #6
0 / 30.0

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