| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 443107 |
2021-07-09T17:30:33 Z |
leaked |
UFO (IZhO14_ufo) |
C++14 |
|
1034 ms |
200476 KB |
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
typedef unsigned long long ull;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=1e5+1;
vec<int>vc;
int k;
struct tree{
vec<int>a;
vec<int>t;
void b_tr(int v,int tl,int tr){
if(tl==tr){
t[v]=a[tl];
return;
}
else{
int tm=(tl+tr)>>1;
b_tr(2*v,tl,tm);b_tr(2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
}
void init(vec<int> b){
a=b;
t.resize(sz(a)*4);
b_tr(1,0,sz(a)-1);
}
void upd(int id,int x,int v,int tl,int tr){
if(tl==tr){
t[v]=x;
return;
}
int tm=(tl+tr)>>1;
if(tm>=id) upd(id,x,2*v,tl,tm);
else upd(id,x,2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
void gol(int x,int v,int tl,int tr){
if(t[v]<x) return;
if(sz(vc)==k) return;
if(tl==tr){
vc.pb(tl);
return;
}
int tm=(tl+tr)>>1;
gol(x,2*v,tl,tm);gol(x,2*v+1,tm+1,tr);
}
void gor(int x,int v,int tl,int tr){
if(t[v]<x) return;
if(sz(vc)==k) return;
if(tl==tr){
vc.pb(tl);
return;
}
int tm=(tl+tr)>>1;
gor(x,2*v+1,tm+1,tr);
gor(x,2*v,tl,tm);
}
};
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m,q,p;
cin>>n>>m>>k>>q>>p;
vec<tree>r(n),c(m);
vec<vec<int>>a(n,vec<int>(m,0));
vec<vec<int>>b(m,vec<int>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
b[j][i]=a[i][j];
}
}
for(int i=0;i<n;i++){
r[i].init(a[i]);
}
for(int i=0;i<m;i++){
c[i].init(b[i]);
}
auto change=[&](int i,int j,int x){
r[i].upd(j,x,1,0,m-1);
c[j].upd(i,x,1,0,n-1);
a[i][j]=x;
};
while(q--){
char ch;
int f,s;
cin>>ch>>f>>s;--f;
vc.clear();
if(ch=='N' || ch=='S'){
if(ch=='N')c[f].gol(s,1,0,n-1);
else c[f].gor(s,1,0,n-1);
for(auto &z : vc){
// cerr<<"THER "<<z<<endl;
change(z,f,a[z][f]-1);
}
}
else{
if(ch=='W')r[f].gol(s,1,0,m-1);
else r[f].gor(s,1,0,m-1);
for(auto &z : vc){
change(f,z,a[f][z]-1);
}
}
}
vec<vec<int>>pref(n,vec<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
pref[i][j]=(j?pref[i][j-1]:0)+a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
pref[i][j]=(i?pref[i-1][j]:0)+pref[i][j];
}
}
auto get=[&](int l1,int r1,int x1,int x2){
int sc=pref[r1][x2];
if(l1) sc-=pref[l1-1][x2];
if(x1) sc-=pref[r1][x1-1];
if(l1 && x1) sc+=pref[l1-1][x1-1];
return sc;
};
// cout<<"ALO"<<endl;
int ans=0;
for(int i=p-1;i<n;i++){
for(int j=p-1;j<m;j++){
// cout<<a[i][j]<<' ';
umax(ans,get(i-p+1,i,j-p+1,j));
}
// cout<<endl;
}
cout<<ans;
return 0;
}
/*
4 8 2 1 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
13 ms |
936 KB |
Output is correct |
| 5 |
Correct |
73 ms |
4044 KB |
Output is correct |
| 6 |
Correct |
163 ms |
28700 KB |
Output is correct |
| 7 |
Correct |
247 ms |
69692 KB |
Output is correct |
| 8 |
Correct |
196 ms |
66160 KB |
Output is correct |
| 9 |
Correct |
377 ms |
60860 KB |
Output is correct |
| 10 |
Correct |
432 ms |
65252 KB |
Output is correct |
| 11 |
Correct |
317 ms |
66780 KB |
Output is correct |
| 12 |
Correct |
446 ms |
65260 KB |
Output is correct |
| 13 |
Correct |
528 ms |
69048 KB |
Output is correct |
| 14 |
Correct |
448 ms |
66924 KB |
Output is correct |
| 15 |
Correct |
532 ms |
66876 KB |
Output is correct |
| 16 |
Correct |
217 ms |
69160 KB |
Output is correct |
| 17 |
Correct |
824 ms |
73460 KB |
Output is correct |
| 18 |
Correct |
207 ms |
68600 KB |
Output is correct |
| 19 |
Correct |
305 ms |
79028 KB |
Output is correct |
| 20 |
Correct |
1034 ms |
200476 KB |
Output is correct |
