Submission #1038549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038549		vjudge1	Seats (IOI18_seats)	C++17	25 / 100	4077 ms	72636 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
struct segtree{
    int Tmn[1<<21],Tmx[1<<21];
    void upd(int i,int l,int r,int p,int x){
        if(l==r)return void(Tmn[i]=Tmx[i]=x);
        if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
        else upd(i*2,l,l+r>>1,p,x);
        Tmn[i]=min(Tmn[i*2+1],Tmn[i*2]);
        Tmx[i]=max(Tmx[i*2],Tmx[i*2+1]);
    }
    int querymx(int i,int l,int r,int rr){
        if(r<=rr)return Tmx[i]; if(l>rr)return-1e9;
        return max(querymx(i*2,l,l+r>>1,rr),
                querymx(i*2+1,l+r+2>>1,r,rr));
    }
    int querymn(int i,int l,int r,int rr){
        if(r<=rr)return Tmn[i]; if(l>rr)return 1e9;
        return min(querymn(i*2,l,l+r>>1,rr),
                querymn(i*2+1,l+r+2>>1,r,rr));
    }
} STr,STc;
int span(int pos){
    int ans=(STr.querymx(1,1,1e6,pos)-STr.querymn(1,1,1e6,pos)+1)*
            (STc.querymx(1,1,1e6,pos)-STc.querymn(1,1,1e6,pos)+1);
    return ans;
}
int ans;
vector<int>R_,C_;
void act(int i){
    STr.upd(1,1,1e6,1+i,R_[i]),
    STc.upd(1,1,1e6,1+i,C_[i]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    R_=R,C_=C;
    for(int i=0;i<H*W;)
        act(i++),ans+=i==span(i);
}
int qry(){
    int ans=0;
    int k=1,sz=R_.size();
    while(k<=sz){
        int c=span(k);
        if(c==k)ans++,c++;
        k=c;
    }
    return ans;
}
int swap_seats(int a, int b) {
    swap(R_[a],R_[b]);
    swap(C_[a],C_[b]);
    act(a),act(b);
    return qry();
}

Compilation message (stderr)

seats.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
seats.cpp:9:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |            ~^~
seats.cpp:9:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |                                ~~~^~
seats.cpp:10:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |         else upd(i*2,l,l+r>>1,p,x);
      |                        ~^~
seats.cpp: In member function 'int segtree::querymx(int, int, int, int)':
seats.cpp:15:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |         if(r<=rr)return Tmx[i]; if(l>rr)return-1e9;
      |         ^~
seats.cpp:15:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |         if(r<=rr)return Tmx[i]; if(l>rr)return-1e9;
      |                                 ^~
seats.cpp:16:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         return max(querymx(i*2,l,l+r>>1,rr),
      |                                  ~^~
seats.cpp:17:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |                 querymx(i*2+1,l+r+2>>1,r,rr));
      |                               ~~~^~
seats.cpp: In member function 'int segtree::querymn(int, int, int, int)':
seats.cpp:20:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |         if(r<=rr)return Tmn[i]; if(l>rr)return 1e9;
      |         ^~
seats.cpp:20:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |         if(r<=rr)return Tmn[i]; if(l>rr)return 1e9;
      |                                 ^~
seats.cpp:21:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         return min(querymn(i*2,l,l+r>>1,rr),
      |                                  ~^~
seats.cpp:22:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |                 querymn(i*2+1,l+r+2>>1,r,rr));
      |                               ~~~^~

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