Submission #757301

#	Time	Username	Problem	Language	Result	Execution time	Memory
757301		WifeCake	Seats (IOI18_seats)	C++14	0 / 100	245 ms	15932 KiB

seats

#pragma GCC optiomiz("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
#define REP(i,a,n) for(int i=a;i<n;++i)
#define RE1(i,a,n) for(int i=a;i<=n;++i)
#define SR1(i,a,n) for(int i=a;i>=n;--i)
#define F first
#define S second
#define mp make_pair
#define mtp make_tuple
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()
#define Sheeesh cin.tie(0),ios::sync_with_stdio(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()+1);

class ST
{
    int n;
    vector<pii> zkw; // {min,amo}
    vector<int> tg;

    void upd(int k,int w)
    {
        zkw[k].F+=k;
        tg[k]+=w;
    }
    void pull(int p)
    {
        for(;p>1;p>>=1)
            if(zkw[p<<1].F==zkw[p<<1|1].F)
                zkw[p]=mp( zkw[p<<1].F+tg[p] ,zkw[p<<1].S+zkw[p<<1|1].S );
            else
            {
                zkw[p] = (zkw[p<<1].F < zkw[p<<1|1].F) ? zkw[p<<1] : zkw[p<<1|1] ;
                zkw[p].F+=tg[p];
            }
    }
    void push(int p)
    {
        RE1(h,0,__lg(p))
        {
            auto k=p>>h;
            if(tg[k>>1])
            {
                upd(k,tg[k>>1]);
                upd(k^1,tg[k>>1]);
                tg[k>>1]=0;
            }
        }
    }
public:
    void init(int _n)
    {
        n=_n;
        zkw.resize(n<<1);
        tg.resize(n<<1);
        REP(i,0,n)
            zkw[i+n].S=1;
        SR1(i,n-1,1)
            zkw[i].S=zkw[i<<1].S+zkw[i<<1|1].S;
    }
    void MDF(pii p,int w)
    {
        auto[l,r]=p;
        auto cl=l,cr=r;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1)
        {
            if(l&1)
                upd(l++,w);
            if(!(r&1))
                upd(r--,w);
        }
        pull(cl+n),pull(cr+n);
    }
    int QRY()
    {
        return zkw[1].S;
    }
}g;
int r,c;
vector<int> loc,st;

pii cul(int k)
{
    auto l=min(st[k],st[k+1]);
    auto r=min(st[k],st[k+1]);
    return mp(l,r-1);
}

void give_initial_chart(int _r,int _c,vector<int> R,vector<int> C)
{
    r=_r,c=_c;

    // r=x, c=1
    if(r!=1)
        exit(0);

    loc.resize(c);
    st.resize(c+2);
    st.front()=st.back()=c;
    REP(i,0,c)
    {
        loc[i]=C[i]+1;
        st[C[i]+1]=i;
    }
    REP(i,0,c)
        g.MDF(cul(i),1);
}

int swap_seats(int a,int b)
{
    auto la=loc[a],lb=loc[b];
    g.MDF(cul(la),-1);
    g.MDF(cul(la-1),-1);
    g.MDF(cul(lb),-1);
    g.MDF(cul(lb-1),-1);

    swap(st[la],st[lb]);
    swap(loc[a],loc[b]);

    g.MDF(cul(la),1);
    g.MDF(cul(la-1),1);
    g.MDF(cul(lb),1);
    g.MDF(cul(lb-1),1);
    return g.QRY();
}

Compilation message (stderr)

seats.cpp:1: warning: ignoring '#pragma GCC optiomiz' [-Wunknown-pragmas]
    1 | #pragma GCC optiomiz("Ofast")
      | 
seats.cpp: In member function 'void ST::MDF(pii, int)':
seats.cpp:67:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         auto[l,r]=p;
      |             ^

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