oj.uz

Submission #875200

# Submission time Handle Problem Language Result Execution time Memory
875200 2023-11-18T19:02:52 Z abcvuitunggio Seats (IOI18_seats) C++17
33 / 100
 1018 ms 106756 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct T{
    pair <int, int> mn,sum;
    int cnt;
}st[4000001];
int n;
vector <int> r,c;
vector <vector <int>> a;
T operator +(T a, T b){
    T c;
    b.mn.first+=a.sum.first;
    b.mn.second+=a.sum.second;
    c.mn=min(a.mn,b.mn);
    c.cnt=0;
    if (c.mn==a.mn)
        c.cnt+=a.cnt;
    if (c.mn==b.mn)
        c.cnt+=b.cnt;
    c.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
    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;
}
pair <int, int> calc(int i){
    int res=0,res2=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]);
            res2+=(i==v[2])-(i==v[3]);
        }
    return {res,res2};
}
void build(int node, int l, int r){
    if (l==r){
        st[node].mn=st[node].sum=calc(l);
        st[node].cnt=1;
        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].mn=st[node].sum=calc(i);
        st[node].cnt=1;
        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:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     return (i<0||i>=a.size()||j<0||j>=a[0].size()?n:a[i][j]);
      |                  ~^~~~~~~~~~
seats.cpp:25:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     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 45 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 78940 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 162 ms 79568 KB Output is correct
2 Correct 202 ms 79872 KB Output is correct
3 Correct 240 ms 79564 KB Output is correct
4 Correct 275 ms 79728 KB Output is correct
5 Correct 321 ms 79856 KB Output is correct
6 Correct 981 ms 106500 KB Output is correct
7 Correct 1014 ms 106504 KB Output is correct
8 Correct 1014 ms 106660 KB Output is correct
9 Correct 1018 ms 106320 KB Output is correct
10 Correct 936 ms 106580 KB Output is correct
11 Correct 929 ms 106756 KB Output is correct
12 Correct 897 ms 106580 KB Output is correct

Subtask #6
0 / 30.0

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