제출 #1215720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215720		Gabp	Rectangles (IOI19_rect)	C++20	컴파일 에러	0 ms	0 KiB

rect

#include<bits/stdc++.h>
using namespace std;

struct SegTree {
  vector<int> st;
  
  SegTree(int n) {
    st.assign(4 * n, 0);
  }
  
  void update(int v, int tl, int tr, int idx, int add) {
    if (tl == tr) {
      st[v] += add;
      return;
    }
    
    int mid = tl + (tr - tl) / 2;
    if (idx <= mid) update(2 * v, tl, mid, idx, add);
    else update(2 * v + 1, mid + 1, tr, idx, add);
    st[v] = st[2 * v] + st[2 * v + 1];
  }
  
  int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) return st[v];
    
    int mid = tl + (tr - tl) / 2;
    return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
  }
};

long long int count_rectangles(vector<vector<int>> a) {
  int n = a.size();
  int m = a[0].size();
  
  vector<set<int>> row(n), col(m);
  vector<vector<map<int,int>>> dp_row(n, vector<map<int,int>>(m));
  vector<vector<map<int,int>>> dp_col = dp_row;
  
  vector<tuple<int,int,int>> b;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      b.emplace_back(a[i][j], i, j);
    }
  }
  sort(b.begin(), b.end());
  
  for (int i = 0; i < n; i++) {
    row[i].insert(-1);
    row[i].insert(m);
  }
  for (int i = 0; i < m; i++) {
    col[i].insert(-1);
    col[i].insert(n);
  }
  
  int p = 0;
  while (p < n * m) {
    int curr = get<0>(b[p]);
    int start = p;
    while (p < n * m && get<0>(b[p]) == curr) {
      auto [_, i, j] = b[p++];
      row[i].insert(j);
      col[j].insert(i);
    }
    
    for (int i = start; i < p; i++) {
      auto [_, x, y] = b[i];
      
      // row
      {
        auto it = row[x].find(y);
        it--;
        if (*it && y - *it > 1) {
          int l = (*it) + 1;
          int r = y - 1;
          dp_row[x][l][r] = -x;
        }
        it++;
        it++;
        if (*it != m && (*it) - y > 1) {
          int l = y + 1;
          int r = (*it) - 1;
          dp_row[x][l][r] = -x;
        }
      }
      
      // col
      {
        auto it = col[y].find(x);
        it--;
        if (*it && x - *it > 1) {
          int l = (*it) + 1;
          int r = x - 1;
          dp_col[l][y][-r] = y;
        }
        it++;
        it++;
        if (*it != n && (*it) - x > 1) {
          int l = x + 1;
          int r = (*it) - 1;
          dp_col[l][y][-r] = y;
        }
      }
    }
  }
  
  SegTree st(m);
  long long int ans = 0;
  for (int i = n - 2; i > 0; i--) {
    for (int j = m - 2; j > 0; j--) {
      if (j + 2 < m) {
        for (auto [idx, _]: dp_col[i][j]) {
          if (dp_col[i][j + 1].count(idx)) dp_col[i][j][idx] = dp_col[i][j][idx + 1];
        }
      }
      
      vector<pair<int,int>> order;
      for (auto [idx, _]: dp_row[i][j]) {
        if (i + 2 < n && dp_row[i + 1][j].count(idx)) dp_row[i][j][idx] = dp_row[i + 1][j][idx];
        order.emplace_back(dp_row[i][j][idx], idx);
      }
      sort(order.begin(), order.end());
      
      int p = 0;
      for (auto [idx, r]) {
        while (p < order.size() && order[p].first <= idx) {
          st.update(1, 0, m - 1, order[p++].second, 1);
        }
        
        ans += st.query(1, 0, m - 1, j, r);
      }
      for (auto [_, idx]: order) st.update(1, 0, m - 1, idx, -1);
    }
  }
  
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:126:25: error: expected initializer before ')' token
  126 |       for (auto [idx, r]) {
      |                         ^
rect.cpp:126:25: error: expected ';' before ')' token
  126 |       for (auto [idx, r]) {
      |                         ^
      |                         ;
rect.cpp:126:25: error: expected primary-expression before ')' token
rect.cpp:126:25: error: expected ';' before ')' token
  126 |       for (auto [idx, r]) {
      |                         ^
      |                         ;