Submission #454553

#	Time	Username	Problem	Language	Result	Execution time	Memory
454553		ftkbrian	Seats (IOI18_seats)	C++14	5 / 100	4078 ms	56780 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pll pair<ll,ll>
#define f first
#define s second
vector<pll> X;
ll nm,inf = 1e9;
pll ST[2][4040404];
pll hp(pll a,pll b) { return {max(a.f,b.f),min(a.s,b.s)}; }
void upd(ll t,ll id,ll s,ll e,ll L,ll v) {
    if(s > L || L > e) return;
    if(s == e) { ST[t][id] = {v,v}; return; }
    ll m = s+e>>1;
    upd(t,id*2,s,m,L,v); upd(t,id*2+1,m+1,e,L,v);
    ST[t][id] = hp(ST[t][id*2],ST[t][id*2+1]);
}
pll hap(ll t,ll dx,ll s,ll e,ll qs,ll qe) {
    if(s > qe || e < qs) return {-inf,inf};
    if(qs <= s && e <= qe) return ST[t][dx];
    ll m = s+e>>1;
    return hp(hap(t,dx*2,s,m,qs,qe),hap(t,dx*2+1,m+1,e,qs,qe));
}
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
    for(int i = 0 ; i < r.size() ; i++) X.push_back({r[i],c[i]});
    nm = X.size();
    for(int i = 0 ; i < nm ; i++) {
        upd(0,1,0,nm-1,i,X[i].f);
        upd(1,1,0,nm-1,i,X[i].s);
    }
}

int swap_seats(int a, int b) {
    swap(X[a],X[b]);
    upd(0,1,0,nm-1,a,X[a].f);
    upd(0,1,0,nm-1,b,X[b].f);
    upd(1,1,0,nm-1,a,X[a].s);
    upd(1,1,0,nm-1,b,X[b].s);
    int s = 1,ret = 1;
    while(s < nm) {
        pll A = hap(0,1,0,nm-1,0,s);
        pll B = hap(1,1,0,nm-1,0,s);
        if((A.f-A.s+1)*(B.f-B.s+1) == s+1) ret++,s+=min(A.f-A.s+1,B.f-B.s+1);
        else s = (A.f-A.s+1)*(B.f-B.s+1)-1;
    }
    return ret;
}

Compilation message (stderr)

seats.cpp: In function 'void upd(ll, ll, ll, ll, ll, ll)':
seats.cpp:15:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     ll m = s+e>>1;
      |             ^
seats.cpp: In function 'std::pair<int, int> hap(ll, ll, ll, ll, ll, ll)':
seats.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll m = s+e>>1;
      |             ^
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0 ; i < r.size() ; i++) X.push_back({r[i],c[i]});
      |                     ~~^~~~~~~~~~

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