| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 837069 | Ellinor | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
//#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i < b; i++)
#define rrep(i,a) for (int i = (a) - 1; i >= 0; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<bool, bool> pbb;
// fast
#include "aliens.h" // !!!
//
int N, M;
vector<int> diagonal;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
N = n;
M = m;
diagonal.assign(M, 0); // -1 ?
rep(i,0,N)
{
int d = min(r[i], c[i]);
int da = max(r[i], c[i]) - min(r[i], c[i]) + 1; // +1 // 0-ind
diagonal[d] = max(diagonal[d], da);
}
int d = 0;
rep(i,0,M)
{
d--;
// d = max(d, 0);
d = max(d, diagonal[i]);
diagonal[i] = d;
}
set<pii> square_start_inds;
int last = 0;
rep(i,0,M)
{
last = max(last, 0);
if (diagonal[i] > last)
{
// start of square
square_start_inds.insert({i, diagonal[i]});
last = diagonal[i];
}
last--;
}
// squares > 0
if (square_start_inds.size() > k)
{
// diff // diff, start_ind_1, start_ind_2
set<array<ll, 3>> diff_set;
map<pii, ll> diff_map; // ??
auto it = square_start_inds.begin();
pii x = *it;
int last_ind = x.first;
int last_len = x.second;
int now_ind, now_len;
for (auto it = square_start_inds.begin(); it != square_start_inds.end(); it++)
{
it++;
x = *it;
now_ind = x.first;
now_len = x.second;
ll diff = 0;
ll side = now_ind + now_len - last_ind; // 1 1
ll add = side * side;
diff += add;
ll rem = last_len * last_len;
diff -= rem;
rem = now_len * now_len;
diff -= rem;
//
diff_set.insert({diff, last_ind, now_ind});
diff_map[{last_ind, now_ind}] = diff;
//
last_ind = x.first;
last_len = x.second;
}
while (square_start_inds.size() > k)
{
// assert(diff_set.size() > 0); // :)
// assert(diff_set.size() == square_start_inds.size() - 1); // :)
auto it = diff_set.begin();
array<ll, 3> arr = *it;
ll diff = arr[0];
ll ind_1 = arr[1];
ll ind_2 = arr[2];
diff_set.erase(it); // !
ll ind_2_len;
bool before = false, after = false;
ll ind_before, len_before;
auto itt = square_start_inds.lower_bound({ind_1, 0});
if (itt != square_start_inds.begin())
{
before = true;
itt--;
pii x = *itt;
ind_before = x.first;
len_before = x.second;
ll diff1 = diff_map[{ind_before, ind_1}];
auto it1 = diff_set.lower_bound({diff1, ind_before, ind_1});
// assert !
diff_set.erase(it1);
// square_start_inds.erase(itt); // bort nej
// ta bort diff
}
// else ?
ll ind_after, len_after;
// ta bort diff
// ???
itt = square_start_inds.lower_bound({ind_2, 0});
// !
pii xx = *itt;
ind_2_len = xx.second;
if (itt != square_start_inds.end())
{
itt++;
if (itt != square_start_inds.end())
{
after = true;
pii x = *itt;
ind_after = x.first;
len_after = x.second;
ll diff2 = diff_map[{ind_2, ind_after}];
auto it2 = diff_set.lower_bound({diff2, ind_2, ind_after});
// assert !
diff_set.erase(it2);
// square_start_inds.erase(itt); // bort nej
// ta bort diff
}
}
ll my_len = ind_2 + ind_2_len - ind_1;
// add new diff 1
if (before)
{
last_ind = ind_before;
last_len = len_before;
now_ind = ind_1;
now_len = my_len;
ll diff_ = 0;
ll side = now_ind + now_len - last_ind; // 1 1
ll add = side * side;
diff_ += add;
ll rem = last_len * last_len;
diff_ -= rem;
rem = now_len * now_len;
diff_ -= rem;
diff_set.insert({diff_, last_ind, now_ind});
diff_map[{last_ind, now_ind}] = diff_;
}
// add new diff 2
if (after)
{
last_ind = ind_1;
last_len = my_len;
now_ind = ind_after;
now_len = len_after;
diff_ = 0;
side = now_ind + now_len - last_ind; // 1 1
add = side * side;
diff_ += add;
rem = last_len * last_len;
diff_ -= rem;
rem = now_len * now_len;
diff_ -= rem;
diff_set.insert({diff_, last_ind, now_ind});
diff_map[{last_ind, now_ind}] = diff_;
}
// ta bort square_inds * 2, add * 1
// ta bort 1
auto it3 = square_start_inds.lower_bound({ind_1, 0}); // :)
// ?
square_start_inds.erase(it3);
// ta bort 2
// ???
it3 = square_start_inds.lower_bound({ind_2, 0}); // :)
// ?
square_start_inds.erase(it3);
// add 1
square_start_inds.insert({ind_1, my_len});
}
}
ll ans = 0;
ll last_reach = -1;
for (auto it = square_start_inds.begin(); it != square_start_inds.end(); it++)
{
pii x = *it;
ll add = x.second * x.second;
ans += add;
if (last_reach >= x.first)
{
int overlap = last_reach - x.first + 1;
ll rem = overlap * overlap;
ans -= rem;
}
last_reach = x.first + x.second - 1;
}
return ans;
}