oj.uz

Submission #880661

# Submission time Handle Problem Language Result Execution time Memory
880661 2023-11-29T19:43:57 Z mychecksedad Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 1184 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+1)*(j-i+1) - (j-i+2)/2) 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 344 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 344 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 580 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 24 ms 348 KB Output is correct
10 Correct 502 ms 552 KB Output is correct
11 Correct 71 ms 508 KB Output is correct
12 Correct 70 ms 344 KB Output is correct
13 Correct 149 ms 348 KB Output is correct
14 Correct 153 ms 512 KB Output is correct
15 Correct 80 ms 508 KB Output is correct
16 Correct 17 ms 348 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 344 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 580 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 24 ms 348 KB Output is correct
10 Correct 502 ms 552 KB Output is correct
11 Correct 71 ms 508 KB Output is correct
12 Correct 70 ms 344 KB Output is correct
13 Correct 149 ms 348 KB Output is correct
14 Correct 153 ms 512 KB Output is correct
15 Correct 80 ms 508 KB Output is correct
16 Correct 17 ms 348 KB Output is correct
17 Correct 2130 ms 1184 KB Output is correct
18 Correct 224 ms 604 KB Output is correct
19 Correct 16 ms 348 KB Output is correct
20 Execution timed out 5099 ms 876 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 344 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 580 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 24 ms 348 KB Output is correct
10 Correct 502 ms 552 KB Output is correct
11 Correct 71 ms 508 KB Output is correct
12 Correct 70 ms 344 KB Output is correct
13 Correct 149 ms 348 KB Output is correct
14 Correct 153 ms 512 KB Output is correct
15 Correct 80 ms 508 KB Output is correct
16 Correct 17 ms 348 KB Output is correct
17 Correct 2130 ms 1184 KB Output is correct
18 Correct 224 ms 604 KB Output is correct
19 Correct 16 ms 348 KB Output is correct
20 Execution timed out 5099 ms 876 KB Time limit exceeded
21 Halted 0 ms 0 KB -