oj.uz

Submission #880650

# Submission time Handle Problem Language Result Execution time Memory
880650 2023-11-29T19:34:51 Z mychecksedad Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 3512 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;
  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:99:15: warning: unused variable 'aa' [-Wunused-variable]
   99 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 5045 ms 3512 KB Time limit exceeded
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 356 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 356 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 93 ms 576 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 48 ms 488 KB Output is correct
10 Correct 512 ms 556 KB Output is correct
11 Correct 76 ms 348 KB Output is correct
12 Correct 83 ms 560 KB Output is correct
13 Correct 657 ms 348 KB Output is correct
14 Correct 341 ms 348 KB Output is correct
15 Correct 176 ms 536 KB Output is correct
16 Correct 42 ms 492 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 356 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 93 ms 576 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 48 ms 488 KB Output is correct
10 Correct 512 ms 556 KB Output is correct
11 Correct 76 ms 348 KB Output is correct
12 Correct 83 ms 560 KB Output is correct
13 Correct 657 ms 348 KB Output is correct
14 Correct 341 ms 348 KB Output is correct
15 Correct 176 ms 536 KB Output is correct
16 Correct 42 ms 492 KB Output is correct
17 Correct 2260 ms 1244 KB Output is correct
18 Correct 551 ms 648 KB Output is correct
19 Correct 28 ms 648 KB Output is correct
20 Execution timed out 5024 ms 1056 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 356 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 93 ms 576 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 48 ms 488 KB Output is correct
10 Correct 512 ms 556 KB Output is correct
11 Correct 76 ms 348 KB Output is correct
12 Correct 83 ms 560 KB Output is correct
13 Correct 657 ms 348 KB Output is correct
14 Correct 341 ms 348 KB Output is correct
15 Correct 176 ms 536 KB Output is correct
16 Correct 42 ms 492 KB Output is correct
17 Correct 2260 ms 1244 KB Output is correct
18 Correct 551 ms 648 KB Output is correct
19 Correct 28 ms 648 KB Output is correct
20 Execution timed out 5024 ms 1056 KB Time limit exceeded
21 Halted 0 ms 0 KB -