# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
866665 | nasir_bashirov | 삶의 질 (IOI10_quality) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "quality.h"
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
struct fenwickTree{
int n;
vi BIT;
fenwickTree(int sz){
n = sz;
BIT.resize(n + 1, 0);
}
void update(int i, int v){
if(i == 0) return;
while(i <= n){
BIT[i] += v;
i += i & (-i);
}
}
int query(int l, int r){
if(l > r) return 0;
if(l != 1) return query(1, r) - query(1, l - 1);
int res = 0;
while(r > 0){
res += BIT[r];
r -= r & (-r);
}
return res;
}
};
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int rectangle(int r, int c, int h, int w, int Q[3001][3001]) {
int res = 1e9, tt = 0;
for(int i = 1; i <= r - h + 1; i++){
ordered_set st;
for(int a = 1; a < w; a++){
for(int b = i; b <= i + h - 1; b++){
st.insert({Q[b - 1][a - 1], t++});
}
}
for(int a = w; a <= c; a++){
for(int b = i; b <= i + h - 1; b++){
st.insert({Q[b - 1][a - 1], t++});
}
if(a > w){
for(int b = i; b <= i + h - 1; b++){
st.erase(st.lowerbound({Q[b - 1][a - w - 1], 0}));
}
}
res = min(res, (*st.find_by_order(h * w / 2)).first);
}
}
return res;
}