제출 #1038565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038565		vjudge1	Seats (IOI18_seats)	C++17	33 / 100	542 ms	82264 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct segtree{
    struct DDT{
        int mn,mnc,lz,l,r;
        DDT(){mnc=1,mn=lz=0;}
        DDT(DDT a,DDT b){
            *this=a;
            if(b.mn<mn)
                mn=b.mn,mnc=0;
            if(b.mn==mn)
                mnc+=b.mnc;
        }
    } T[1<<21];
    void pd(int i){
        int k=T[i].lz;
        if(k){T[i].lz=0,
            T[i].mn+=k;
            if(i<1<<20)
                T[i*2].lz+=k,
                T[i*2+1].lz+=k;
        }
    }
    void upd(int i,int l,int r,int ll,int rr,int v){
        pd(i);if(ll<=l&&r<=rr)
            return T[i].lz=v,pd(i);
        if(ll>r||l>rr) return;
        upd(i*2,l,l+r>>1,ll,rr,v);
        upd(i*2+1,l+r+2>>1,r,ll,rr,v);
        T[i]=DDT(T[i*2],T[i*2+1]);
        T[i].l=l,T[i].r=r;
    }
} ST;
vector<int>C_;
int app[1000100];
bitset<1000100>had;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    for(auto&i:C)i++;
    C.insert(C.begin(),0);
    C_=C;
    int ranges=0;
    memset(app,1,sizeof app);
    for(int i=1;i<=H*W;i++){
        ranges++;
        app[C[i]]=i;
        had[C[i]]=1;
        ranges-=had[C[i]-1];
        ranges-=had[C[i]+1];
        ST.upd(1,1,H*W,i,i,ranges);
    }
}
inline void do_contrib(int l,int r,int coef){
    int v=C_[l];
    int a=app[v-1],b=app[v+1];
    ST.upd(1,1,C_.size()-1,l,r,coef);
    ST.upd(1,1,C_.size()-1,max(a,l),r,-coef);
    ST.upd(1,1,C_.size()-1,max(b,l),r,-coef);
}
int swap_seats(int a, int b) {
    a++;b++; if(a>b)swap(a,b);
    do_contrib(a,b-1,-1);
    swap(C_[a],C_[b]);
    app[C_[a]]=a;
    app[C_[b]]=b;
    do_contrib(a,b-1,1);
    return ST.T[1].mnc;
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In member function 'void segtree::upd(int, int, int, int, int, int)':
seats.cpp:29:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         upd(i*2,l,l+r>>1,ll,rr,v);
      |                   ~^~
seats.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         upd(i*2+1,l+r+2>>1,r,ll,rr,v);
      |                   ~~~^~

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