| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 917508 |
2024-01-28T11:00:55 Z |
8pete8 |
UFO (IZhO14_ufo) |
C++17 |
|
710 ms |
172668 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6+5,Mxn=1e8,inf=1e9,minf=-1e9,lg=30;
int n,m,r,k,p;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
struct seg{
vector<int>v;
void init(int n){v.resize(4*n+4,minf);}
void upd(int l,int r,int pos,int val,int up){
if(l==r)return void(v[pos]=val);
int mid=l+(r-l)/2;
if(up<=mid)upd(l,mid,pos*2,val,up);
else upd(mid+1,r,pos*2+1,val,up);
v[pos]=max(v[pos*2],v[pos*2+1]);
}
void update(int pos,int val,int n){
upd(1,n,1,val,pos);
}
int qry1(int l,int r,int ql,int qr,int h,int pos){
int mid=l+(r-l)/2;
if(l>qr||r<ql)return inf;
if(v[pos]<h)return inf;
if(l==r)return r;
int ans=qry1(l,mid,ql,qr,h,pos*2);
if(ans!=inf)return ans;
return qry1(mid+1,r,ql,qr,h,pos*2+1);
}
int qry2(int l,int r,int ql,int qr,int h,int pos){
int mid=l+(r-l)/2;
if(l>qr||r<ql)return inf;
if(v[pos]<h)return inf;
if(l==r)return r;
int ans=qry2(mid+1,r,ql,qr,h,pos*2+1);
if(ans!=inf)return ans;
return qry2(l,mid,ql,qr,h,pos*2);
}
}t[2][mxn+10];
int get1(int d,int h,int n,int p,int last){
return t[d][p].qry1(1,n,last+1,n,h,1);
}
int get2(int d,int h,int n,int p,int last){
return t[d][p].qry2(1,n,1,last-1,h,1);
}
int32_t main(){
fastio
cin>>n>>m>>r>>k>>p;
vector<vector<int>>grid(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];
for(int i=1;i<=n;i++){
t[0][i].init(m);
for(int j=1;j<=m;j++)t[0][i].update(j,grid[i][j],m);
}
for(int j=1;j<=m;j++){
t[1][j].init(n);
for(int i=1;i<=n;i++)t[1][j].update(i,grid[i][j],n);
}
int d=0,sz=0,cnt,last,x,y;
bool yes=false;
while(k--){
char g;cin>>g;
int p,h;cin>>p>>h;
if(g=='W'||g=='E')d=0,sz=m;
else d=1,sz=n;
if(g=='W'||g=='N')yes=true,last=0;
else yes=false,last=sz+1;
cnt=r;
while(cnt--){
last=((yes)?get1(d,h,sz,p,last):get2(d,h,sz,p,last));
if(last==inf||last==minf)break;
x=p,y=last;
if(d)swap(x,y);
grid[x][y]--;
t[0][x].update(y,grid[x][y],m);
t[1][y].update(x,grid[x][y],n);
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)grid[i][j]+=grid[i][j-1]+grid[i-1][j]-grid[i-1][j-1];
int ans=0;
for(int i=p;i<=n;i++)for(int j=p;j<=m;j++)ans=max(ans,grid[i][j]-grid[i-p][j]-grid[i][j-p]+grid[i-p][j-p]);
cout<<ans;
}
Compilation message
ufo.cpp:31:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
31 | #pragma GCC optimize ("03,unroll-lopps")
| ^
ufo.cpp:36:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
36 | void setIO(string name){
| ^
ufo.cpp:43:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
43 | void init(int n){v.resize(4*n+4,minf);}
| ^
ufo.cpp:44:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
44 | void upd(int l,int r,int pos,int val,int up){
| ^
ufo.cpp:51:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
51 | void update(int pos,int val,int n){
| ^
ufo.cpp:54:53: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
54 | int qry1(int l,int r,int ql,int qr,int h,int pos){
| ^
ufo.cpp:63:52: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
63 | int qry2(int l,int r,int ql,int qr,int h,int pos){
| ^
ufo.cpp:73:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
73 | int get1(int d,int h,int n,int p,int last){
| ^
ufo.cpp:76:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
76 | int get2(int d,int h,int n,int p,int last){
| ^
ufo.cpp:79:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
79 | int32_t main(){
| ^
ufo.cpp: In function 'void setIO(std::string)':
ufo.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
47196 KB |
Output is correct |
| 2 |
Correct |
16 ms |
47444 KB |
Output is correct |
| 3 |
Correct |
16 ms |
47452 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47964 KB |
Output is correct |
| 5 |
Correct |
75 ms |
51240 KB |
Output is correct |
| 6 |
Correct |
154 ms |
82004 KB |
Output is correct |
| 7 |
Correct |
242 ms |
123452 KB |
Output is correct |
| 8 |
Correct |
197 ms |
123384 KB |
Output is correct |
| 9 |
Correct |
437 ms |
120776 KB |
Output is correct |
| 10 |
Correct |
462 ms |
123200 KB |
Output is correct |
| 11 |
Correct |
351 ms |
121764 KB |
Output is correct |
| 12 |
Correct |
489 ms |
123200 KB |
Output is correct |
| 13 |
Correct |
593 ms |
126504 KB |
Output is correct |
| 14 |
Correct |
410 ms |
121780 KB |
Output is correct |
| 15 |
Correct |
427 ms |
123200 KB |
Output is correct |
| 16 |
Correct |
213 ms |
121708 KB |
Output is correct |
| 17 |
Correct |
604 ms |
126288 KB |
Output is correct |
| 18 |
Correct |
201 ms |
118188 KB |
Output is correct |
| 19 |
Correct |
279 ms |
128840 KB |
Output is correct |
| 20 |
Correct |
710 ms |
172668 KB |
Output is correct |
