Submission #770272

#	Time	Username	Problem	Language	Result	Execution time	Memory
770272		boyliguanhan	Seats (IOI18_seats)	C++17	25 / 100	4086 ms	65612 KiB

seats

#include "seats.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c,d;
} val[4000100];
int l[4000100], r[4000100];
node join(node a, node b){
    node c;
    c.a = min(a.a,b.a);
    c.b = max(a.b,b.b);
    c.c = min(a.c,b.c);
    c.d = max(a.d,b.d);
    return c;
}
void build(int i, int rl, int rr) {
    l[i] = rl, r[i] = rr;
    if(rl!=rr)
        build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
}
void upd(int i, int pos, int x, int y) {
    if(l[i]==r[i])
        return(void) (val[i].a=val[i].b=x,val[i].c=val[i].d=y);
    if(pos>r[i*2])
        upd(i*2+1,pos,x,y);
    else upd(i*2,pos,x,y);
    val[i]=join(val[i*2],val[i*2+1]);
}
node query(int i, int x, int y) {
    if(x<=l[i]&&r[i]<=y)
        return val[i];
    if(x>r[i]||l[i]>y)
        return (node){1000000,0,1000000,0};
    return join(query(i*2,x,y),query(i*2+1,x,y));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    build(1,1,H*W);
    for(int i = 0; i < r[1]; i++) {
        upd(1,i+1,R[i],C[i]);
    }
}
int swap_seats(int a, int b) {
    a++,b++;
    node x = query(1,a,a), y = query(1,b,b);
    upd(1,b,x.a,x.c);
    upd(1,a,y.a,y.c);
    int ans = 0;
    for(int i = 1; i <= r[1]; i++) {
        x=query(1,1,i);
        int sz = (x.b-x.a+1)*(x.d-x.c+1);
        if(sz==i) ans++;
        else i = max(i,sz-1);
    }
    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:20:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
      |                      ~~^~~
seats.cpp:20:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, 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