oj.uz

Submission #173754

# Submission time Handle Problem Language Result Execution time Memory
173754 2020-01-05T10:04:46 Z AlexLuchianov Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 459876 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 2500;
int v[1 + nmax][1 + nmax];
int n, m;

namespace Dsu{
std::vector<int> mult;
std::vector<int> sz;
std::vector<int> maxid;
std::vector<int> minid;
void initialize(int n){
  mult.resize(1 + n);
  sz.resize(1 + n);
  maxid.resize(1 + n);
  minid.resize(1 + n);
  for(int i = 1;i <= n; i++){
    minid[i] = maxid[i] = mult[i] = i;
    sz[i] = 1;
  }
}

int jump(int gala){
  if(gala != mult[gala])
    mult[gala] = jump(mult[gala]);
  return mult[gala];
}

void unite(int gala, int galb){
  gala = jump(gala);
  galb = jump(galb);
  if(gala == galb)
    return ;
  if(sz[galb] < sz[gala])
    std::swap(gala, galb);
  sz[galb] += sz[gala];
  mult[gala] = galb;
  maxid[galb] = MAX(maxid[gala], maxid[galb]);
  minid[galb] = MIN(minid[gala], minid[galb]);
}

}

std::vector<int> orizontal[1 + nmax][1 + nmax];
std::vector<int> vertical[1 + nmax][1 + nmax];

std::map<std::tuple<int,int,int>, int> freq;

struct Update{
  int type;
  int x;
  int y;
  int time;
  bool operator < (Update const &a) const{
    if(time != a.time)
      return time < a.time;
    else
      return type < a.type;
  }
};

int scount[1 + nmax][1 + (int)sqrt(nmax)];

ll solvelevel(int level){
  std::map<std::pair<int,int>, int> freq2;

  std::vector<Update> updates;
  //std::cout << "Solve: " << level << '\n';
  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < orizontal[level][i].size(); h++){
      int lim = orizontal[level][i][h];
      freq[std::make_tuple(level, i, lim)] = freq[std::make_tuple(level + 1, i, lim)] + 1;
      updates.push_back({1, i, lim, -freq[std::make_tuple(level, i, lim)]});
      //std::cout << ":";
    }
  }

  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < vertical[level][i].size(); h++){
      int lim = vertical[level][i][h];
      freq2[{i, lim}] = freq2[{i - 1, lim}] + 1;
    }
  }

  //std::cout << "verticals:\n";
  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < vertical[level][i].size(); h++){
      int lim = vertical[level][i][h];
     //  std::cout << level << " " << i << " " << vertical[level][i][h] << "| ";
      if(0 == freq2[{i + 1, lim}]){
        updates.push_back({2, i - freq2[{i, lim}] + 1, i, -(lim - level + 1) });
      }
    }
  }
  //std::cout << ":";
  sort(updates.begin(), updates.end());

  std::vector<Update> onlyupdates;

  int rad = sqrt(m);
  ll result = 0;

  for(int i = 1;i <= m; i++)
    for(int j = 0; j <= rad; j++)
      scount[i][0] = 0;

 // std::cout << vertical[28][20].size() << '\n';

  for(int i = 0; i < updates.size(); i++){
    Update curr = updates[i];
    //std::cout << curr.type << " " << curr.x << " " << curr.y << " " << -curr.time<< '\n';
    if(curr.type == 1){
      onlyupdates.push_back(curr);
      int x = curr.x, y = curr.y;
      while(1 <= x){
        scount[x][y - x]++;
        x--;
      }
    } else {
      /*
      if((curr.y - curr.x) <= rad){
        for(int j = curr.x; j <= curr.y; j++)
          result += scount[curr.x][j - curr.x];
      } else {
      */
        for(int j = 0; j < onlyupdates.size(); j++){
          if(curr.x <= onlyupdates[j].x && onlyupdates[j].y <= curr.y)
            result++;
        }
      //}
    }
  }

  //std::cout << level << " " << result << '\n';
  return result;
}

long long count_rectangles(std::vector<std::vector<int> > a){
  n = a.size();
  m = a[0].size();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      v[i][j] = a[i][j];
  for(int i = 1; i < n - 1; i++){
    std::vector<std::pair<int,int>> temp;
    for(int j = 1;j < m - 1; j++)
      temp.push_back({v[i][j], j});
    sort(temp.begin(), temp.end());
    Dsu::initialize(m);
    for(int j = 0; j < temp.size(); j++){
      int pos = temp[j].second;
      if(v[i][pos - 1] <= v[i][pos])
        Dsu::unite(pos - 1, pos);
      if(v[i][pos + 1] < v[i][pos])
        Dsu::unite(pos + 1, pos);
      int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
      if(v[i][x - 1] > v[i][pos] && v[i][pos] < v[i][y + 1])
        orizontal[i][x].push_back(y);
    }
  }

  for(int i = 1; i < m - 1; i++){
    std::vector<std::pair<int,int>> temp;
    for(int j = 1;j < n - 1; j++)
      temp.push_back({v[j][i], j});
    sort(temp.begin(), temp.end());
    Dsu::initialize(n);
    for(int j = 0; j < temp.size(); j++){
      int pos = temp[j].second;
      if(v[pos - 1][i] <= v[pos][i])
        Dsu::unite(pos - 1, pos);
      if(v[pos + 1][i] < v[pos][i])
        Dsu::unite(pos + 1, pos);
      int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
      //std::cout << i << " " << x << " " << y << '\n';
      if(v[x - 1][i] > v[pos][i] && v[pos][i] < v[y + 1][i])
        vertical[x][i].push_back(y);
    }
  }
  ll result = 0;
  for(int i = n - 2; 1 <= i; i--)
    result += solvelevel(i);
  return result;
}

Compilation message

rect.cpp: In function 'll solvelevel(int)':
rect.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < orizontal[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < updates.size(); i++){
                  ~~^~~~~~~~~~~~~~~~
rect.cpp:133:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < onlyupdates.size(); j++){
                        ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < temp.size(); j++){
                    ~~^~~~~~~~~~~~~
rect.cpp:175:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < temp.size(); j++){
                    ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 294192 KB Output is correct
2 Correct 283 ms 294364 KB Output is correct
3 Correct 280 ms 294412 KB Output is correct
4 Correct 279 ms 294392 KB Output is correct
5 Correct 276 ms 294264 KB Output is correct
6 Correct 278 ms 294316 KB Output is correct
7 Correct 280 ms 294264 KB Output is correct
8 Correct 280 ms 294216 KB Output is correct
9 Correct 281 ms 294408 KB Output is correct
10 Correct 276 ms 294392 KB Output is correct
11 Correct 279 ms 294576 KB Output is correct
12 Correct 280 ms 294496 KB Output is correct
13 Correct 274 ms 294136 KB Output is correct
14 Correct 274 ms 294264 KB Output is correct
15 Correct 274 ms 294236 KB Output is correct
16 Correct 275 ms 294136 KB Output is correct
17 Correct 290 ms 294156 KB Output is correct
18 Correct 275 ms 294140 KB Output is correct
19 Correct 276 ms 294372 KB Output is correct
20 Correct 275 ms 294392 KB Output is correct
21 Correct 274 ms 294136 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 294192 KB Output is correct
2 Correct 283 ms 294364 KB Output is correct
3 Correct 280 ms 294412 KB Output is correct
4 Correct 279 ms 294392 KB Output is correct
5 Correct 276 ms 294264 KB Output is correct
6 Correct 278 ms 294316 KB Output is correct
7 Correct 280 ms 294264 KB Output is correct
8 Correct 280 ms 294216 KB Output is correct
9 Correct 281 ms 294408 KB Output is correct
10 Correct 276 ms 294392 KB Output is correct
11 Correct 279 ms 294576 KB Output is correct
12 Correct 280 ms 294496 KB Output is correct
13 Correct 274 ms 294136 KB Output is correct
14 Correct 274 ms 294264 KB Output is correct
15 Correct 274 ms 294236 KB Output is correct
16 Correct 275 ms 294136 KB Output is correct
17 Correct 281 ms 295384 KB Output is correct
18 Correct 290 ms 295444 KB Output is correct
19 Correct 285 ms 295380 KB Output is correct
20 Correct 286 ms 294904 KB Output is correct
21 Correct 286 ms 295404 KB Output is correct
22 Correct 285 ms 295416 KB Output is correct
23 Correct 287 ms 295416 KB Output is correct
24 Correct 279 ms 294776 KB Output is correct
25 Correct 290 ms 294156 KB Output is correct
26 Correct 275 ms 294140 KB Output is correct
27 Correct 276 ms 294372 KB Output is correct
28 Correct 275 ms 294392 KB Output is correct
29 Correct 274 ms 294136 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 294192 KB Output is correct
2 Correct 283 ms 294364 KB Output is correct
3 Correct 280 ms 294412 KB Output is correct
4 Correct 279 ms 294392 KB Output is correct
5 Correct 276 ms 294264 KB Output is correct
6 Correct 278 ms 294316 KB Output is correct
7 Correct 280 ms 294264 KB Output is correct
8 Correct 280 ms 294216 KB Output is correct
9 Correct 281 ms 294408 KB Output is correct
10 Correct 276 ms 294392 KB Output is correct
11 Correct 279 ms 294576 KB Output is correct
12 Correct 280 ms 294496 KB Output is correct
13 Correct 274 ms 294136 KB Output is correct
14 Correct 274 ms 294264 KB Output is correct
15 Correct 274 ms 294236 KB Output is correct
16 Correct 275 ms 294136 KB Output is correct
17 Correct 281 ms 295384 KB Output is correct
18 Correct 290 ms 295444 KB Output is correct
19 Correct 285 ms 295380 KB Output is correct
20 Correct 286 ms 294904 KB Output is correct
21 Correct 286 ms 295404 KB Output is correct
22 Correct 285 ms 295416 KB Output is correct
23 Correct 287 ms 295416 KB Output is correct
24 Correct 279 ms 294776 KB Output is correct
25 Correct 323 ms 300664 KB Output is correct
26 Correct 325 ms 300572 KB Output is correct
27 Correct 323 ms 300664 KB Output is correct
28 Correct 310 ms 298160 KB Output is correct
29 Correct 352 ms 301256 KB Output is correct
30 Correct 355 ms 301304 KB Output is correct
31 Correct 349 ms 300632 KB Output is correct
32 Correct 347 ms 300636 KB Output is correct
33 Correct 290 ms 294156 KB Output is correct
34 Correct 275 ms 294140 KB Output is correct
35 Correct 276 ms 294372 KB Output is correct
36 Correct 275 ms 294392 KB Output is correct
37 Correct 274 ms 294136 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 294192 KB Output is correct
2 Correct 283 ms 294364 KB Output is correct
3 Correct 280 ms 294412 KB Output is correct
4 Correct 279 ms 294392 KB Output is correct
5 Correct 276 ms 294264 KB Output is correct
6 Correct 278 ms 294316 KB Output is correct
7 Correct 280 ms 294264 KB Output is correct
8 Correct 280 ms 294216 KB Output is correct
9 Correct 281 ms 294408 KB Output is correct
10 Correct 276 ms 294392 KB Output is correct
11 Correct 279 ms 294576 KB Output is correct
12 Correct 280 ms 294496 KB Output is correct
13 Correct 274 ms 294136 KB Output is correct
14 Correct 274 ms 294264 KB Output is correct
15 Correct 274 ms 294236 KB Output is correct
16 Correct 275 ms 294136 KB Output is correct
17 Correct 281 ms 295384 KB Output is correct
18 Correct 290 ms 295444 KB Output is correct
19 Correct 285 ms 295380 KB Output is correct
20 Correct 286 ms 294904 KB Output is correct
21 Correct 286 ms 295404 KB Output is correct
22 Correct 285 ms 295416 KB Output is correct
23 Correct 287 ms 295416 KB Output is correct
24 Correct 279 ms 294776 KB Output is correct
25 Correct 323 ms 300664 KB Output is correct
26 Correct 325 ms 300572 KB Output is correct
27 Correct 323 ms 300664 KB Output is correct
28 Correct 310 ms 298160 KB Output is correct
29 Correct 352 ms 301256 KB Output is correct
30 Correct 355 ms 301304 KB Output is correct
31 Correct 349 ms 300632 KB Output is correct
32 Correct 347 ms 300636 KB Output is correct
33 Correct 784 ms 352016 KB Output is correct
34 Correct 827 ms 345820 KB Output is correct
35 Correct 747 ms 345984 KB Output is correct
36 Correct 774 ms 340000 KB Output is correct
37 Correct 1103 ms 367504 KB Output is correct
38 Correct 1108 ms 367368 KB Output is correct
39 Correct 1095 ms 367688 KB Output is correct
40 Correct 1036 ms 363132 KB Output is correct
41 Correct 787 ms 326244 KB Output is correct
42 Correct 893 ms 336460 KB Output is correct
43 Correct 1647 ms 375180 KB Output is correct
44 Correct 1699 ms 377848 KB Output is correct
45 Correct 818 ms 337128 KB Output is correct
46 Correct 950 ms 335972 KB Output is correct
47 Correct 1553 ms 366416 KB Output is correct
48 Correct 1872 ms 367560 KB Output is correct
49 Correct 290 ms 294156 KB Output is correct
50 Correct 275 ms 294140 KB Output is correct
51 Correct 276 ms 294372 KB Output is correct
52 Correct 275 ms 294392 KB Output is correct
53 Correct 274 ms 294136 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 295612 KB Output is correct
2 Correct 295 ms 295396 KB Output is correct
3 Correct 283 ms 294736 KB Output is correct
4 Correct 277 ms 294096 KB Output is correct
5 Correct 292 ms 295416 KB Output is correct
6 Correct 286 ms 295488 KB Output is correct
7 Correct 287 ms 295472 KB Output is correct
8 Correct 284 ms 295352 KB Output is correct
9 Correct 281 ms 295288 KB Output is correct
10 Correct 270 ms 294264 KB Output is correct
11 Correct 271 ms 294232 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 294160 KB Output is correct
2 Execution timed out 5055 ms 459876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 294192 KB Output is correct
2 Correct 283 ms 294364 KB Output is correct
3 Correct 280 ms 294412 KB Output is correct
4 Correct 279 ms 294392 KB Output is correct
5 Correct 276 ms 294264 KB Output is correct
6 Correct 278 ms 294316 KB Output is correct
7 Correct 280 ms 294264 KB Output is correct
8 Correct 280 ms 294216 KB Output is correct
9 Correct 281 ms 294408 KB Output is correct
10 Correct 276 ms 294392 KB Output is correct
11 Correct 279 ms 294576 KB Output is correct
12 Correct 280 ms 294496 KB Output is correct
13 Correct 274 ms 294136 KB Output is correct
14 Correct 274 ms 294264 KB Output is correct
15 Correct 274 ms 294236 KB Output is correct
16 Correct 275 ms 294136 KB Output is correct
17 Correct 281 ms 295384 KB Output is correct
18 Correct 290 ms 295444 KB Output is correct
19 Correct 285 ms 295380 KB Output is correct
20 Correct 286 ms 294904 KB Output is correct
21 Correct 286 ms 295404 KB Output is correct
22 Correct 285 ms 295416 KB Output is correct
23 Correct 287 ms 295416 KB Output is correct
24 Correct 279 ms 294776 KB Output is correct
25 Correct 323 ms 300664 KB Output is correct
26 Correct 325 ms 300572 KB Output is correct
27 Correct 323 ms 300664 KB Output is correct
28 Correct 310 ms 298160 KB Output is correct
29 Correct 352 ms 301256 KB Output is correct
30 Correct 355 ms 301304 KB Output is correct
31 Correct 349 ms 300632 KB Output is correct
32 Correct 347 ms 300636 KB Output is correct
33 Correct 784 ms 352016 KB Output is correct
34 Correct 827 ms 345820 KB Output is correct
35 Correct 747 ms 345984 KB Output is correct
36 Correct 774 ms 340000 KB Output is correct
37 Correct 1103 ms 367504 KB Output is correct
38 Correct 1108 ms 367368 KB Output is correct
39 Correct 1095 ms 367688 KB Output is correct
40 Correct 1036 ms 363132 KB Output is correct
41 Correct 787 ms 326244 KB Output is correct
42 Correct 893 ms 336460 KB Output is correct
43 Correct 1647 ms 375180 KB Output is correct
44 Correct 1699 ms 377848 KB Output is correct
45 Correct 818 ms 337128 KB Output is correct
46 Correct 950 ms 335972 KB Output is correct
47 Correct 1553 ms 366416 KB Output is correct
48 Correct 1872 ms 367560 KB Output is correct
49 Correct 297 ms 295612 KB Output is correct
50 Correct 295 ms 295396 KB Output is correct
51 Correct 283 ms 294736 KB Output is correct
52 Correct 277 ms 294096 KB Output is correct
53 Correct 292 ms 295416 KB Output is correct
54 Correct 286 ms 295488 KB Output is correct
55 Correct 287 ms 295472 KB Output is correct
56 Correct 284 ms 295352 KB Output is correct
57 Correct 281 ms 295288 KB Output is correct
58 Correct 270 ms 294264 KB Output is correct
59 Correct 271 ms 294232 KB Output is correct
60 Correct 270 ms 294160 KB Output is correct
61 Execution timed out 5055 ms 459876 KB Time limit exceeded
62 Halted 0 ms 0 KB -