Submission #880661

#TimeUsernameProblemLanguageResultExecution timeMemory
880661mychecksedadSandcastle 2 (JOI22_ho_t5)C++17
15 / 100
5099 ms1184 KiB
/* 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 (stderr)

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