Submission #1044477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044477		happy_node	Seats (IOI18_seats)	C++17	25 / 100	4075 ms	138544 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

const int MX=1e6+5;
const array<int,4> inf={(int)1e9,0,(int)1e9,0};

int H,W;
vector<int> R,C;
array<int,4> arr[MX];

struct segtree {
        array<int,4> t[4*MX];

        array<int,4> merge(array<int,4> l, array<int,4> r) {
                return {min(l[0],r[0]),max(l[1],r[1]),min(l[2],r[2]),max(l[3],r[3])};
        }

        void upd(int v, int l, int r, int pos, array<int,4> val) {
                if(l>r) return; 
                if(pos<l || r<pos) return;
                if(l==r) {
                        t[v]=val;
                        return;
                }
                int m=(l+r)/2;
                upd(v*2+0,l,m+0,pos,val);
                upd(v*2+1,m+1,r,pos,val);
                t[v]=merge(t[2*v+0],t[2*v+1]);
        }

        array<int,4> que(int v, int l, int r, int ql, int qr) {
                if(r<ql || qr<l) return inf;
                if(ql<=l && r<=qr) return t[v];
                int m=(l+r)/2;
                return merge(que(v*2+0,l,m+0,ql,qr),que(v*2+1,m+1,r,ql,qr));
        }

        vector<pair<int,int>> dfs(int v, int l, int r, array<int,4> cur) {
                if(l>r) return {};
                if(t[v]==inf) return {};
                if(l==r) {
                        array<int,4> nxt=merge(cur,arr[l]);
                        return {{l,(nxt[1]-nxt[0]+1)*(nxt[3]-nxt[2]+1)}};
                }

                int m=(l+r)/2;
                vector<pair<int,int>> res;
                if(cur!=merge(cur,t[2*v])) {
                        vector<pair<int,int>> res2=dfs(2*v,l,m,cur);
                        for(auto x:res2) res.push_back(x);
                        res2.clear();
                }

                array<int,4> nxt=merge(cur,t[2*v]);
                if(nxt!=merge(nxt,t[2*v+1])) {
                        vector<pair<int,int>> res2=dfs(2*v+1,m+1,r,nxt);
                        for(auto x:res2) res.push_back(x);
                        res2.clear();
                } 

                return res;
        }

        void prep() {
                for(int i=0;i<4*MX;i++) {
                        t[i]=inf;
                }
        }
} st;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
        ::H=H, ::W=W, ::R=R, ::C=C;

        st.prep();

        for(int i=0;i<H*W;i++) {
                arr[i]={R[i],R[i],C[i],C[i]};
                st.upd(1,0,H*W-1,i,arr[i]);
        }
}

int swap_seats(int a, int b) {
        swap(arr[a],arr[b]);
        st.upd(1,0,H*W-1,a,arr[a]);
        st.upd(1,0,H*W-1,b,arr[b]);

        vector<pair<int,int>> v=st.dfs(1,0,H*W-1,inf);
        v.push_back({H*W,(int)1e9});

        int ans=0;
        for(int i=0;i+1<v.size();i++) {
                int x=v[i].first, y=v[i+1].first;
                int area=v[i].second;
                ans+=x<area && area<=y;
        }

        return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:92:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int i=0;i+1<v.size();i++) {
      |                     ~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30