Submission #108673

#	Time	Username	Problem	Language	Result	Execution time	Memory
108673		RezwanArefin01	Seats (IOI18_seats)	C++17	0 / 100	342 ms	63024 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std; 

const int N = 1e6 + 5; 
vector<int> r; 
int n, m, a[N];

struct node {
    int mn, cnt, lazy; 
    node(int mn = 0, int cnt = 1, int lazy = 0) :
        mn(mn), cnt(cnt), lazy(lazy) {} 
} t[N << 2]; 


void upd(int node, int x) {
    t[node].lazy += x; 
    t[node].mn += x; 
}

void shift(int node) {
    upd(node << 1, t[node].lazy); 
    upd(node << 1 | 1, t[node].lazy); 
    t[node].lazy = 0;
}

node merge(node L, node R) {
    node ret; 
    ret.mn = min(L.mn, R.mn); 
    ret.cnt = L.mn == R.mn ? L.cnt + R.cnt : L.mn < R.mn ? L.cnt : R.cnt;
    return ret ;
}

void build(int node, int l, int r) {
    if(l == r) return; 
    int m = l + r >> 1; 
    build(node << 1, l, m); 
    build(node << 1 | 1, m + 1, r); 
    t[node].cnt = r - l + 1; 
}
void update(int node, int l, int r, int i, int j, int x) {
    if(r < i || l > j || i > j) return;
    if(i <= l && r <= j) {
        upd(node, x); 
        return; 
    } shift(node); 
    int m = l + r >> 1; 
    update(node << 1, l, m, i, j, x); 
    update(node << 1 | 1, m + 1, r, i, j, x); 
    t[node] = merge(t[node << 1], t[node << 1 | 1]); 
}

node query(int node, int l, int r, int i, int j) {
    if(r < i || l > j) return {N, 0, 0};
    if(i <= l && r <= j) return t[node];
    shift(node);
    int m = l + r >> 1; 
    return merge(query(node << 1, l, m, i, j), query(node << 1 | 1, m + 1, r, i, j)); 
}
void change(int i, int x) {
    update(1, 0, n - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]) - 1, -1); 
    update(1, 0, n - 1, min(a[i + 1], a[i]), max(a[i + 1], a[i]) - 1, -1); 
    a[i] = x;
    update(1, 0, n - 1, min(a[i - 1], x), max(a[i - 1], x) - 1, +1); 
    update(1, 0, n - 1, min(a[i + 1], x), max(a[i + 1], x) - 1, +1); 
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = W;
    for(int i = 0; i <= n + 1; ++i) a[i] = n;     
    for(int i = 0; i < n; ++i) {
        change(C[i] + 1, i); 
    }   
}  

int swap_seats(int i, int j) { 
    ++i, ++j;
    int x = a[i], y = a[j]; 
    change(i, n); 
    change(j, n);
    
    change(i, y); 
    change(j, x);
    if(t[1].mn != 2) return 0; 
    else return t[1].cnt; 
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
seats.cpp: In function 'void update(int, int, int, int, int, int)':
seats.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
seats.cpp: In function 'node query(int, int, int, int, int)':
seats.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~

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