oj.uz

Submission #880654

# Submission time Handle Problem Language Result Execution time Memory
880654 2023-11-29T19:35:18 Z mychecksedad Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 1336 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n, m, val;
array<int, 2> pos[N];
vector<vector<int>> v;

int calc(int x, int y){
  return abs(pos[x][0] - pos[y][0]) + abs(pos[x][1] - pos[y][1]) == 1;
}


void upd(int x, set<int> &s){
  auto it = s.upper_bound(x);
  if(s.empty()){
    s.insert(x);
    return;
  }
  if(it == s.begin()){
    val += calc(x, *it);
    s.insert(x);
    return;
  }
  if(it == s.end()){
    auto it1 = prev(it);
    val += calc(x, *it1);
    s.insert(x);
    return;
  }

  auto it1 = prev(it);
  val -= calc(*it, *it1);
  val += calc(x, *it);
  val += calc(x, *it1);
  s.insert(x);
}

void solve(){
  cin >> n >> m;
  if(max(n, m) > 7000) return;
  vector<int> V;
  v.resize(n);
  for(int i = 0; i < n; ++i){
    v[i].resize(m);
    for(int j = 0; j < m; ++j){
      cin >> v[i][j];
      V.pb(v[i][j]);
    }
  }
  if(n > m){
    vector<vector<int>> g;
    g.resize(m);
    for(int i = 0; i < m; ++i){
      g[i].resize(n);
      for(int j = 0; j < n; ++j) g[i][j] = v[j][i];
    }
    g.swap(v);
    swap(n, m);
  }
  sort(all(V));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      v[i][j] = lower_bound(all(V), v[i][j]) - V.begin() + 1;
      pos[v[i][j]] = {i, j};
    }
  }
  int ans = 0;
  for(int i = 0; i < n; ++i){
    for(int j = i; j < n; ++j){
      for(int c = 0; c < m; ++c){
        set<int> s;
        val = 1;
        for(int c1 = c; c1 >= 0; --c1){
          for(int k = i; k <= j; ++k){
            upd(v[k][c1], s);
          }
          if(val == (c-c1+1)*(j-i+1)){
            ans++;
          }
          if(val <= (c-c1)*(j-i+1)) break;
        }
      }
    }
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:100:15: warning: unused variable 'aa' [-Wunused-variable]
  100 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 77 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 49 ms 348 KB Output is correct
10 Correct 493 ms 544 KB Output is correct
11 Correct 81 ms 548 KB Output is correct
12 Correct 71 ms 548 KB Output is correct
13 Correct 642 ms 344 KB Output is correct
14 Correct 333 ms 596 KB Output is correct
15 Correct 181 ms 344 KB Output is correct
16 Correct 38 ms 348 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 77 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 49 ms 348 KB Output is correct
10 Correct 493 ms 544 KB Output is correct
11 Correct 81 ms 548 KB Output is correct
12 Correct 71 ms 548 KB Output is correct
13 Correct 642 ms 344 KB Output is correct
14 Correct 333 ms 596 KB Output is correct
15 Correct 181 ms 344 KB Output is correct
16 Correct 38 ms 348 KB Output is correct
17 Correct 2098 ms 1112 KB Output is correct
18 Correct 520 ms 604 KB Output is correct
19 Correct 28 ms 348 KB Output is correct
20 Execution timed out 5053 ms 1336 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 77 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 49 ms 348 KB Output is correct
10 Correct 493 ms 544 KB Output is correct
11 Correct 81 ms 548 KB Output is correct
12 Correct 71 ms 548 KB Output is correct
13 Correct 642 ms 344 KB Output is correct
14 Correct 333 ms 596 KB Output is correct
15 Correct 181 ms 344 KB Output is correct
16 Correct 38 ms 348 KB Output is correct
17 Correct 2098 ms 1112 KB Output is correct
18 Correct 520 ms 604 KB Output is correct
19 Correct 28 ms 348 KB Output is correct
20 Execution timed out 5053 ms 1336 KB Time limit exceeded
21 Halted 0 ms 0 KB -