Submission #837065

#TimeUsernameProblemLanguageResultExecution timeMemory
837065EllinorAliens (IOI16_aliens)C++14
4 / 100
2078 ms212 KiB
#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) { 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; ll ind_before, len_before; auto itt = square_start_inds.lower_bound({ind_1, 0}); if (itt != square_start_inds.begin()) { 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()) { 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 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 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}); assert(it3 != square_start_inds.end()); // ? square_start_inds.erase(it3); // ta bort 2 // ??? it3 = square_start_inds.lower_bound({ind_2, 0}); assert(it3 != square_start_inds.end()); // ? 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; }

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:80:34: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if (square_start_inds.size() > k)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
aliens.cpp:124:41: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |         while (square_start_inds.size() > k)
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
aliens.cpp:128:16: warning: unused variable 'diff' [-Wunused-variable]
  128 |             ll diff = arr[0];
      |                ^~~~
aliens.cpp:186:22: warning: 'ind_before' may be used uninitialized in this function [-Wmaybe-uninitialized]
  186 |             last_ind = ind_before;
      |             ~~~~~~~~~^~~~~~~~~~~~
aliens.cpp:211:21: warning: 'ind_after' may be used uninitialized in this function [-Wmaybe-uninitialized]
  211 |             now_ind = ind_after;
      |             ~~~~~~~~^~~~~~~~~~~
aliens.cpp:212:21: warning: 'len_after' may be used uninitialized in this function [-Wmaybe-uninitialized]
  212 |             now_len = len_after;
      |             ~~~~~~~~^~~~~~~~~~~
aliens.cpp:187:22: warning: 'len_before' may be used uninitialized in this function [-Wmaybe-uninitialized]
  187 |             last_len = len_before;
      |             ~~~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...