oj.uz

Submission #173770

# Submission time Handle Problem Language Result Execution time Memory
173770 2020-01-05T11:33:28 Z AlexLuchianov Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 662168 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;
  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)]});
    }
  }

  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;
    }
  }

  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < vertical[level][i].size(); h++){
      int lim = vertical[level][i][h];
      if(0 == freq2[{i + 1, lim}]){
        updates.push_back({2, i - freq2[{i, lim}] + 1, i, -(lim - level + 1) });
      }
    }
  }
  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][j] = 0;

  for(int i = 0; i < updates.size(); i++){
    Update curr = updates[i];
    if(curr.type == 1){
      onlyupdates.push_back(curr);
      int x = curr.x, y = curr.y;
      while(1 <= x && y - x <= rad){
        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++;
        }
      }
    }
  }
  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:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < orizontal[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < updates.size(); i++){
                  ~~^~~~~~~~~~~~~~~~
rect.cpp:122: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:144:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < temp.size(); j++){
                    ~~^~~~~~~~~~~~~
rect.cpp:162: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 271 ms 294136 KB Output is correct
2 Correct 266 ms 294296 KB Output is correct
3 Correct 270 ms 294360 KB Output is correct
4 Correct 267 ms 294348 KB Output is correct
5 Correct 265 ms 294264 KB Output is correct
6 Correct 266 ms 294336 KB Output is correct
7 Correct 268 ms 294264 KB Output is correct
8 Correct 267 ms 294132 KB Output is correct
9 Correct 270 ms 294340 KB Output is correct
10 Correct 266 ms 294352 KB Output is correct
11 Correct 266 ms 294336 KB Output is correct
12 Correct 267 ms 294268 KB Output is correct
13 Correct 266 ms 294140 KB Output is correct
14 Correct 267 ms 294380 KB Output is correct
15 Correct 264 ms 294264 KB Output is correct
16 Correct 264 ms 294136 KB Output is correct
17 Correct 270 ms 294092 KB Output is correct
18 Correct 266 ms 294132 KB Output is correct
19 Correct 268 ms 294264 KB Output is correct
20 Correct 266 ms 294224 KB Output is correct
21 Correct 264 ms 294096 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 294136 KB Output is correct
2 Correct 266 ms 294296 KB Output is correct
3 Correct 270 ms 294360 KB Output is correct
4 Correct 267 ms 294348 KB Output is correct
5 Correct 265 ms 294264 KB Output is correct
6 Correct 266 ms 294336 KB Output is correct
7 Correct 268 ms 294264 KB Output is correct
8 Correct 267 ms 294132 KB Output is correct
9 Correct 270 ms 294340 KB Output is correct
10 Correct 266 ms 294352 KB Output is correct
11 Correct 266 ms 294336 KB Output is correct
12 Correct 267 ms 294268 KB Output is correct
13 Correct 266 ms 294140 KB Output is correct
14 Correct 267 ms 294380 KB Output is correct
15 Correct 264 ms 294264 KB Output is correct
16 Correct 264 ms 294136 KB Output is correct
17 Correct 271 ms 295256 KB Output is correct
18 Correct 274 ms 295452 KB Output is correct
19 Correct 276 ms 295372 KB Output is correct
20 Correct 271 ms 294904 KB Output is correct
21 Correct 289 ms 295336 KB Output is correct
22 Correct 279 ms 295416 KB Output is correct
23 Correct 278 ms 295316 KB Output is correct
24 Correct 277 ms 294820 KB Output is correct
25 Correct 270 ms 294092 KB Output is correct
26 Correct 266 ms 294132 KB Output is correct
27 Correct 268 ms 294264 KB Output is correct
28 Correct 266 ms 294224 KB Output is correct
29 Correct 264 ms 294096 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 294136 KB Output is correct
2 Correct 266 ms 294296 KB Output is correct
3 Correct 270 ms 294360 KB Output is correct
4 Correct 267 ms 294348 KB Output is correct
5 Correct 265 ms 294264 KB Output is correct
6 Correct 266 ms 294336 KB Output is correct
7 Correct 268 ms 294264 KB Output is correct
8 Correct 267 ms 294132 KB Output is correct
9 Correct 270 ms 294340 KB Output is correct
10 Correct 266 ms 294352 KB Output is correct
11 Correct 266 ms 294336 KB Output is correct
12 Correct 267 ms 294268 KB Output is correct
13 Correct 266 ms 294140 KB Output is correct
14 Correct 267 ms 294380 KB Output is correct
15 Correct 264 ms 294264 KB Output is correct
16 Correct 264 ms 294136 KB Output is correct
17 Correct 271 ms 295256 KB Output is correct
18 Correct 274 ms 295452 KB Output is correct
19 Correct 276 ms 295372 KB Output is correct
20 Correct 271 ms 294904 KB Output is correct
21 Correct 289 ms 295336 KB Output is correct
22 Correct 279 ms 295416 KB Output is correct
23 Correct 278 ms 295316 KB Output is correct
24 Correct 277 ms 294820 KB Output is correct
25 Correct 319 ms 300544 KB Output is correct
26 Correct 311 ms 300664 KB Output is correct
27 Correct 313 ms 300764 KB Output is correct
28 Correct 304 ms 298232 KB Output is correct
29 Correct 346 ms 301084 KB Output is correct
30 Correct 352 ms 301432 KB Output is correct
31 Correct 337 ms 300720 KB Output is correct
32 Correct 332 ms 300756 KB Output is correct
33 Correct 270 ms 294092 KB Output is correct
34 Correct 266 ms 294132 KB Output is correct
35 Correct 268 ms 294264 KB Output is correct
36 Correct 266 ms 294224 KB Output is correct
37 Correct 264 ms 294096 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 294136 KB Output is correct
2 Correct 266 ms 294296 KB Output is correct
3 Correct 270 ms 294360 KB Output is correct
4 Correct 267 ms 294348 KB Output is correct
5 Correct 265 ms 294264 KB Output is correct
6 Correct 266 ms 294336 KB Output is correct
7 Correct 268 ms 294264 KB Output is correct
8 Correct 267 ms 294132 KB Output is correct
9 Correct 270 ms 294340 KB Output is correct
10 Correct 266 ms 294352 KB Output is correct
11 Correct 266 ms 294336 KB Output is correct
12 Correct 267 ms 294268 KB Output is correct
13 Correct 266 ms 294140 KB Output is correct
14 Correct 267 ms 294380 KB Output is correct
15 Correct 264 ms 294264 KB Output is correct
16 Correct 264 ms 294136 KB Output is correct
17 Correct 271 ms 295256 KB Output is correct
18 Correct 274 ms 295452 KB Output is correct
19 Correct 276 ms 295372 KB Output is correct
20 Correct 271 ms 294904 KB Output is correct
21 Correct 289 ms 295336 KB Output is correct
22 Correct 279 ms 295416 KB Output is correct
23 Correct 278 ms 295316 KB Output is correct
24 Correct 277 ms 294820 KB Output is correct
25 Correct 319 ms 300544 KB Output is correct
26 Correct 311 ms 300664 KB Output is correct
27 Correct 313 ms 300764 KB Output is correct
28 Correct 304 ms 298232 KB Output is correct
29 Correct 346 ms 301084 KB Output is correct
30 Correct 352 ms 301432 KB Output is correct
31 Correct 337 ms 300720 KB Output is correct
32 Correct 332 ms 300756 KB Output is correct
33 Correct 734 ms 352060 KB Output is correct
34 Correct 752 ms 345976 KB Output is correct
35 Correct 693 ms 345936 KB Output is correct
36 Correct 688 ms 339748 KB Output is correct
37 Correct 875 ms 367484 KB Output is correct
38 Correct 867 ms 367420 KB Output is correct
39 Correct 875 ms 367624 KB Output is correct
40 Correct 850 ms 362968 KB Output is correct
41 Correct 605 ms 326136 KB Output is correct
42 Correct 732 ms 336504 KB Output is correct
43 Correct 1277 ms 374980 KB Output is correct
44 Correct 1242 ms 377832 KB Output is correct
45 Correct 740 ms 336888 KB Output is correct
46 Correct 739 ms 335992 KB Output is correct
47 Correct 1126 ms 366240 KB Output is correct
48 Correct 1125 ms 367692 KB Output is correct
49 Correct 270 ms 294092 KB Output is correct
50 Correct 266 ms 294132 KB Output is correct
51 Correct 268 ms 294264 KB Output is correct
52 Correct 266 ms 294224 KB Output is correct
53 Correct 264 ms 294096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 295532 KB Output is correct
2 Correct 271 ms 295380 KB Output is correct
3 Correct 272 ms 294908 KB Output is correct
4 Correct 270 ms 294264 KB Output is correct
5 Correct 274 ms 295416 KB Output is correct
6 Correct 272 ms 295416 KB Output is correct
7 Correct 274 ms 295508 KB Output is correct
8 Correct 271 ms 295416 KB Output is correct
9 Correct 272 ms 295520 KB Output is correct
10 Correct 271 ms 294212 KB Output is correct
11 Correct 269 ms 294136 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 294096 KB Output is correct
2 Correct 2422 ms 460012 KB Output is correct
3 Execution timed out 5053 ms 662168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 294136 KB Output is correct
2 Correct 266 ms 294296 KB Output is correct
3 Correct 270 ms 294360 KB Output is correct
4 Correct 267 ms 294348 KB Output is correct
5 Correct 265 ms 294264 KB Output is correct
6 Correct 266 ms 294336 KB Output is correct
7 Correct 268 ms 294264 KB Output is correct
8 Correct 267 ms 294132 KB Output is correct
9 Correct 270 ms 294340 KB Output is correct
10 Correct 266 ms 294352 KB Output is correct
11 Correct 266 ms 294336 KB Output is correct
12 Correct 267 ms 294268 KB Output is correct
13 Correct 266 ms 294140 KB Output is correct
14 Correct 267 ms 294380 KB Output is correct
15 Correct 264 ms 294264 KB Output is correct
16 Correct 264 ms 294136 KB Output is correct
17 Correct 271 ms 295256 KB Output is correct
18 Correct 274 ms 295452 KB Output is correct
19 Correct 276 ms 295372 KB Output is correct
20 Correct 271 ms 294904 KB Output is correct
21 Correct 289 ms 295336 KB Output is correct
22 Correct 279 ms 295416 KB Output is correct
23 Correct 278 ms 295316 KB Output is correct
24 Correct 277 ms 294820 KB Output is correct
25 Correct 319 ms 300544 KB Output is correct
26 Correct 311 ms 300664 KB Output is correct
27 Correct 313 ms 300764 KB Output is correct
28 Correct 304 ms 298232 KB Output is correct
29 Correct 346 ms 301084 KB Output is correct
30 Correct 352 ms 301432 KB Output is correct
31 Correct 337 ms 300720 KB Output is correct
32 Correct 332 ms 300756 KB Output is correct
33 Correct 734 ms 352060 KB Output is correct
34 Correct 752 ms 345976 KB Output is correct
35 Correct 693 ms 345936 KB Output is correct
36 Correct 688 ms 339748 KB Output is correct
37 Correct 875 ms 367484 KB Output is correct
38 Correct 867 ms 367420 KB Output is correct
39 Correct 875 ms 367624 KB Output is correct
40 Correct 850 ms 362968 KB Output is correct
41 Correct 605 ms 326136 KB Output is correct
42 Correct 732 ms 336504 KB Output is correct
43 Correct 1277 ms 374980 KB Output is correct
44 Correct 1242 ms 377832 KB Output is correct
45 Correct 740 ms 336888 KB Output is correct
46 Correct 739 ms 335992 KB Output is correct
47 Correct 1126 ms 366240 KB Output is correct
48 Correct 1125 ms 367692 KB Output is correct
49 Correct 269 ms 295532 KB Output is correct
50 Correct 271 ms 295380 KB Output is correct
51 Correct 272 ms 294908 KB Output is correct
52 Correct 270 ms 294264 KB Output is correct
53 Correct 274 ms 295416 KB Output is correct
54 Correct 272 ms 295416 KB Output is correct
55 Correct 274 ms 295508 KB Output is correct
56 Correct 271 ms 295416 KB Output is correct
57 Correct 272 ms 295520 KB Output is correct
58 Correct 271 ms 294212 KB Output is correct
59 Correct 269 ms 294136 KB Output is correct
60 Correct 265 ms 294096 KB Output is correct
61 Correct 2422 ms 460012 KB Output is correct
62 Execution timed out 5053 ms 662168 KB Time limit exceeded
63 Halted 0 ms 0 KB -