이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
template<typename Lhs, typename Rhs> inline void Max_self(Lhs &a, Rhs b) { a = (a > b ? a : b); }
template<typename Lhs, typename Rhs> inline void Min_self(Lhs &a, Rhs b) { a = (a < b ? a : b); }
const int N = 5e5 + 10;
int LEN, n;
vector<vector<int>> door;
namespace sub1_2 {
bool check() {
for(int i = 0; i < n; ++ i) if(door[i].size() != 1) return false;
return true;
}
void solve() {
int best = 0;
for(int i = 0; i < n; ++ i) {
Max_self(best, door[i][0]);
}
int res = 2 * max(0, best - (LEN / 2));
if(res > 0) res -= (LEN & 1);
cout << res;
}
}
namespace sub3_4 {
bool check() {
bool check_sub = false;
if(LEN <= 1000000 && n == 2) check_sub = true;
int cnt_door = 0;
for(int i = 0; i < n; ++ i) cnt_door += door[i].size();
if(LEN <= 1000 && cnt_door <= 1000) check_sub = true;
return check_sub;
}
vector<vector<int>> pred;
int sum_to(int l, int r, int idx) {
if(l > r) return 0;
if(l == 0) return pred[idx][r];
return pred[idx][r] - pred[idx][l - 1];
}
bool calc_line(int idx) {
for(int i = 0; i < n; ++ i) {
const auto& psy = pred[i];
int first = lower_bound(psy.begin(), psy.end(), idx) - psy.begin();
int len_last = sum_to(first, psy.size() - 1, i);
if(LEN - len_last + 1 <= idx) return false;
}
return true;
}
void solve() {
for(int i = 0; i < n; ++ i) {
auto psy = door[i];
vector<int> tmp(psy.size());
for(int j = 0; j < psy.size(); ++ j) {
if(j == 0) tmp[j] = psy[j];
else tmp[j] = tmp[j - 1] + psy[j];
}
pred.push_back(tmp);
}
int res = 0;
for(int i = 1; i <= LEN; ++ i) res += calc_line(i);
cout << LEN - res;
}
}
namespace sub5 {
bool check() {
return LEN <= 1000000;
}
struct state {
int v = 0, w = 0, last = 0, idx = 0;
state() {};
state(int _v, int _w, int _last, int _idx) { v = _v; w = _w; last = _last; idx = _idx; };
bool operator < (const state& other) const {
return this -> w < other.w;
}
};
vector<int> pred;
void solve() {
vector<state> buffer = {};
multiset<int, greater<int>> mst = {};
for(int i = 0; i < n; ++ i) {
auto psy = door[i];
vector<int> tmp(psy.size());
for(int j = 0; j < psy.size(); ++ j) {
if(j == 0) tmp[j] = psy[j];
else tmp[j] = tmp[j - 1] + psy[j];
buffer.push_back(state(j, tmp[j], (j == 0 ? 0 : tmp[j - 1]), i));
}
mst.insert(tmp.back());
pred.push_back(tmp.back());
}
sort(buffer.begin(), buffer.end());
int res = 0;
for(int i = 1, j = 0; i <= LEN; ++ i) {
while(j < buffer.size() && buffer[j].w < i) {
auto psy = buffer[j];
auto tmp = mst.find(pred[psy.idx] - psy.last);
if(tmp != mst.end()) mst.erase(tmp);
else assert(false);
mst.insert(pred[psy.idx] - psy.w);
++ j;
}
int first_right = LEN - *mst.begin() + 1;
if(first_right > i) res++;
}
cout << LEN - res;
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("lasers.inp", "r")) {
freopen("lasers.inp", "r", stdin);
freopen("lasers.out", "w", stdout);
}
cin >> LEN >> n;
for(int i = 1; i <= n; ++ i) {
int cnt; cin >> cnt;
vector<int> tmp(cnt);
for(int j = 0; j < cnt; ++ j) cin >> tmp[j];
door.push_back(tmp);
}
if(sub1_2::check()) {
sub1_2::solve();
return 0;
}
if(sub3_4::check()) {
sub3_4::solve();
return 0;
}
if(sub5::check()) {
sub5::solve();
return 0;
}
assert(false);
return 0;
}
/// Code by vuavisao
컴파일 시 표준 에러 (stderr) 메시지
lasers.cpp: In function 'void sub3_4::solve()':
lasers.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j = 0; j < psy.size(); ++ j) {
| ~~^~~~~~~~~~~~
lasers.cpp: In function 'void sub5::solve()':
lasers.cpp:99:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j = 0; j < psy.size(); ++ j) {
| ~~^~~~~~~~~~~~
lasers.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sub5::state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while(j < buffer.size() && buffer[j].w < i) {
| ~~^~~~~~~~~~~~~~~
lasers.cpp: In function 'int32_t main()':
lasers.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen("lasers.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
lasers.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen("lasers.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |