제출 #1106670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106670		snpmrnhlol	Seats (IOI18_seats)	C++17	0 / 100	1190 ms	78912 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15e2;
struct nod{
    int mn,mx;
}seg[2][4*N*N];
nod operator+(nod a, nod b){
    return {min(a.mn,b.mn),max(a.mx,b.mx)};
}
int sz;
void upd(int pos, int x, int y, int l = 0, int r = sz - 1, int node = 1){
    if(l == r){
        seg[0][node] = {x, x};
        seg[1][node] = {y, y};
    }else{
        int mij = (l + r)/2;
        if(pos <= mij){
            upd(pos, x, y, l, mij, node*2);
        }else{
            upd(pos, x, y, mij + 1, r, node*2 + 1);
        }
        seg[0][node] = seg[0][node*2] + seg[0][node*2 + 1];
        seg[1][node] = seg[1][node*2] + seg[1][node*2 + 1];
    }
}
pair<nod,nod> operator+(pair<nod,nod> a, pair<nod,nod> b){
    return {a.first + b.first, a.second + b.second};
}
pair<nod,nod> query(int ql, int qr, int l = 0, int r = sz - 1, int node = 1){
    if(ql <= l && r <= qr){
        return {seg[0][node], seg[1][node]};
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            return query(ql, qr, l, mij, node*2);
        }else if(mij <= ql + 1){
            return query(ql, qr, mij + 1, r, node*2 + 1);
        }else{
            return query(ql, qr, l, mij, node*2) + query(ql, qr, mij + 1, r, node*2 + 1);
        }
    }
}
std::vector<std::vector<int>> v;
vector <int> x,y;
int n,m;
void give_initial_chart(int n2, int m2, std::vector<int> a, std::vector<int> b) {
    n = n2;m = m2;
    v.assign(n, vector<int>(m,0));
    x = a;
    y = b;
    sz = n*m;
    for(int i = 0;i < n*m;i++){
        v[x[i]][y[i]] = i;
        upd(i, x[i], y[i]);
    }
}

int swap_seats(int a, int b){
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    upd(a, x[a], y[a]);
    upd(b, x[b], y[b]);
    int ans = 0;
    int r = -1,l = m,d = -1,u = n;
    int i = 0;
    while(i < n*m){
        pair<nod,nod> p = query(0, i);
        int matrixsz = (p.second.mx - p.second.mn + 1)*(p.first.mx - p.first.mn + 1);
        if(matrixsz == i + 1){
            ans++;
        }
        //cout<<i<<' '<<matrixsz<<'\n';
        i = max(i + 1, matrixsz - 1);
    }
    return ans;
}
/**
2 3 1
0 0
1 0
1 1
0 1
0 2
1 2
0 5
**/

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

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:65:9: warning: unused variable 'r' [-Wunused-variable]
   65 |     int r = -1,l = m,d = -1,u = n;
      |         ^
seats.cpp:65:16: warning: unused variable 'l' [-Wunused-variable]
   65 |     int r = -1,l = m,d = -1,u = n;
      |                ^
seats.cpp:65:22: warning: unused variable 'd' [-Wunused-variable]
   65 |     int r = -1,l = m,d = -1,u = n;
      |                      ^
seats.cpp:65:29: warning: unused variable 'u' [-Wunused-variable]
   65 |     int r = -1,l = m,d = -1,u = n;
      |                             ^

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