Submission #1017521

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10175212024-07-09 08:39:02BestCrazyNoobRectangles (IOI19_rect)C++17
100 / 100
3444 ms419044 KiB
#include "rect.h"
#include <utility>
#include <tuple>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int MAXN = 2'500;
int N, M;
struct SegTreeMax {
int sz;
vector<pii> tree; // min, index (min(a, b) works)
int ql, qr;
void merge(int i) {
tree[i] = max(tree[2*i], tree[2*i+1]);
}
SegTreeMax(vector<int> V) {
sz = 1;
while (sz < V.size()) sz *= 2;
tree.resize(2*sz);
for (int i = 0; i < V.size(); i++) tree[sz+i] = {V[i], i};
for (int i = V.size(); i < sz; i++) tree[sz+i] = {-1, -1};
for (int i = sz-1; i >= 1; i--) merge(i);
}
pii __query(int ni, int nl, int nr) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

rect.cpp: In constructor 'SegTreeMax::SegTreeMax(std::vector<int>)':
rect.cpp:24:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   while (sz < V.size()) sz *= 2;
      |          ~~~^~~~~~~~~~
rect.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i = 0; i < V.size(); i++) tree[sz+i] = {V[i], i};
      |                   ~~^~~~~~~~~~
rect.cpp: In lambda function:
rect.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   if (l != 0 && r != V.size()) res.push_back({l-1, r});
      |                 ~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:165:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |    for (int a = 0, b = 0; b < byEnd[j].size(); b++) {
      |                           ~~^~~~~~~~~~~~~~~~~
rect.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     while (a < grid[i+1][j-1].size() && grid[i+1][j-1][a] >= active[byEnd[j][b]][j].first - 1) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...