oj.uz

Submission #880662

# Submission time Handle Problem Language Result Execution time Memory
880662 2023-11-29T19:47:14 Z mychecksedad Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 1340 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)-3) 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 0 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 344 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 0 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 76 ms 588 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 51 ms 476 KB Output is correct
10 Correct 500 ms 552 KB Output is correct
11 Correct 72 ms 540 KB Output is correct
12 Correct 74 ms 552 KB Output is correct
13 Correct 668 ms 540 KB Output is correct
14 Correct 355 ms 604 KB Output is correct
15 Correct 210 ms 348 KB Output is correct
16 Correct 42 ms 500 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 76 ms 588 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 51 ms 476 KB Output is correct
10 Correct 500 ms 552 KB Output is correct
11 Correct 72 ms 540 KB Output is correct
12 Correct 74 ms 552 KB Output is correct
13 Correct 668 ms 540 KB Output is correct
14 Correct 355 ms 604 KB Output is correct
15 Correct 210 ms 348 KB Output is correct
16 Correct 42 ms 500 KB Output is correct
17 Correct 2124 ms 1340 KB Output is correct
18 Correct 552 ms 604 KB Output is correct
19 Correct 47 ms 572 KB Output is correct
20 Execution timed out 5043 ms 1128 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 76 ms 588 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 51 ms 476 KB Output is correct
10 Correct 500 ms 552 KB Output is correct
11 Correct 72 ms 540 KB Output is correct
12 Correct 74 ms 552 KB Output is correct
13 Correct 668 ms 540 KB Output is correct
14 Correct 355 ms 604 KB Output is correct
15 Correct 210 ms 348 KB Output is correct
16 Correct 42 ms 500 KB Output is correct
17 Correct 2124 ms 1340 KB Output is correct
18 Correct 552 ms 604 KB Output is correct
19 Correct 47 ms 572 KB Output is correct
20 Execution timed out 5043 ms 1128 KB Time limit exceeded
21 Halted 0 ms 0 KB -