Submission #917497

#	Time	Username	Problem	Language	Result	Execution time	Memory
917497		8pete8	UFO (IZhO14_ufo)	C++17	95 / 100	2073 ms	102188 KiB

ufo

#include<stdio.h>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
#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,bruh;
struct seg{
    vector<int>v;
    void init(int n){v.resize(2*n+2,minf);}
    void update(int pos,int val,int n){
        pos+=n+1;
        v[pos]=val;
        for(int i=pos;i>0;i>>=1)v[i>>1]=max(v[i],v[i^1]);
    }
    int qry(int l,int r,int n){
        int ans=minf;
        for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
            if(l&1)ans=max(ans,v[l++]);
            if(!(r&1))ans=max(ans,v[r--]);
        }
        return ans;
    }
}t[2][mxn+10];
int get1(int d,int h,int n,int p,int last){
    int l=last+1,r=n,mid=0,ans=inf;
    while(l<=r){
        mid=l+(r-l)/2;
        if(t[d][p].qry(last+1,mid,n)>=h)ans=min(ans,mid),r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int get2(int d,int h,int n,int p,int last){
    int l=1,r=last-1,mid=0,ans=minf;
    while(l<=r){
        mid=l+(r-l)/2;
        if(t[d][p].qry(mid,last-1,n)>=h)ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int32_t main(){
    scanf("%d %d %d %d %d",&n,&m,&r,&k,&p);
    vector<vector<ll>>grid(n+1,vector<ll>(m+1,0));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&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,po,h;
    char g;
    bool yes=false;
    while(k--){
        scanf(" %c %d %d",&g,&po,&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,po,last):get2(d,h,sz,po,last));
            if(last==inf||last==minf)break;
            x=po,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];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)grid[i][j]+=grid[i-1][j];
    ll 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]);
    printf("%lld",ans);
}

Compilation message (stderr)

ufo.cpp:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
ufo.cpp:40:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 |     void init(int n){v.resize(2*n+2,minf);}
      |                    ^
ufo.cpp:41:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   41 |     void update(int pos,int val,int n){
      |                                      ^
ufo.cpp:46:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     int qry(int l,int r,int n){
      |                              ^
ufo.cpp:55:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 | int get1(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:64:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 | int get2(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:73:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int32_t main(){
      |              ^
ufo.cpp: In function 'int32_t main()':
ufo.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d %d %d %d %d",&n,&m,&r,&k,&p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:76:52: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&grid[i][j]);
      |                                               ~~~~~^~~~~~~~~~~~~~~~~~~~
ufo.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf(" %c %d %d",&g,&po,&h);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 95 / 100