Submission #1113232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113232		8pete8	Misspelling (JOI22_misspelling)	C++17	0 / 100	1 ms	592 KiB

misspelling

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#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 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=5e5+5,inf=1e18,minf=-1e18,lg=30;
int n,k,m,q;
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);
}
int forw[mxn+10],backw[mxn+10],lastf[mxn+10],lastb[mxn+10];
int dp[mxn+10][26][3],sum[mxn+10][26];
struct seg{
    int v[2*mxn+10];
    void init(){
        for(int i=0;i<=2*n;i++)v[i]=0;
    }
    void update(int pos,int val){
        pos+=n;
        v[pos]=max(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 ans=minf;
        for(l+=n,r+=n;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;
int32_t main(){
    fastio 
    cin>>n>>m;
    vector<pii>v1,v2;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        if(a<b)forw[a]=max(forw[a],b),v1.pb({a,b}); //increase (i<-i+1)
        else backw[b]=max(backw[b],a),v2.pb({b,a});//decrease
    }
    sort(rall(v1));
    sort(rall(v2));
    for(auto i:v1){
        forw[i.f]=max(t.qry(i.f,i.s),i.s);
        t.update(i.f,forw[i.f]);
    }
    t.init();
    for(auto i:v2){
        backw[i.f]=max(t.qry(i.f,i.s),i.s);
        t.update(i.f,backw[i.f]);
    }
    for(int i=0;i<26;i++){
        dp[n][i][0]=1;
        sum[n][i]=1;
        if(i)sum[n][i]+=sum[n][i-1];
    }
    for(int i=n-1;i>=1;i--){
        for(int j=0;j<26;j++){
            dp[i][j][0]=dp[i+1][j][0];
            //stay the same
            if(j)dp[i][j][1]=(sum[i+1][j-1]);
            dp[i][j][1]=(dp[i][j][1]+dp[i+1][j][1])%mod;
            //increase
            dp[i][j][2]=(sum[i+1][25]-sum[i+1][j]+mod)%mod;
            dp[i][j][2]=(dp[i][j][2]+dp[i+1][j][2])%mod;
            //decrease
        }
        if(forw[i]&&backw[i]){
            for(int j=0;j<26;j++){
                dp[i][j][1]=dp[i][j][2]=0;
                dp[i][j][1]=(dp[i][j][1]+dp[i][backw[i]][1])%mod;
                dp[i][j][2]=(dp[i][j][2]+dp[i][forw[i]][2])%mod;
            }
        }
        else if(forw[i]){
            for(int j=0;j<26;j++){
                dp[i][j][2]=0;
                dp[i][j][2]=dp[forw[i]][j][2];
            }
        }
        else if(backw[i]){
            for(int j=0;j<26;j++){
                dp[i][j][1]=0;
                dp[i][j][1]=dp[backw[i]][j][1];
            }
        }
        for(int j=0;j<26;j++){
            for(int k=0;k<3;k++)sum[i][j]=(sum[i][j]+dp[i][j][k])%mod;
            if(j)sum[i][j]=(sum[i][j]+sum[i][j-1])%mod;
        }
    }
    int ans=0;
    for(int j=0;j<26;j++)for(int k=0;k<3;k++)ans=(ans+dp[1][j][k])%mod;
    cout<<ans;
}
/*
5 4
1 5
2 4
5 3
5 4
*/

Compilation message (stderr)

misspelling.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
misspelling.cpp:35:35: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   35 | const int mod=1e9+7,mxn=5e5+5,inf=1e18,minf=-1e18,lg=30;
      |                                   ^~~~
misspelling.cpp:35:45: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   35 | const int mod=1e9+7,mxn=5e5+5,inf=1e18,minf=-1e18,lg=30;
      |                                             ^~~~~
misspelling.cpp:37:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   37 | void setIO(string name){
      |                       ^
misspelling.cpp:46:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     void init(){
      |               ^
misspelling.cpp:49:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 |     void update(int pos,int val){
      |                                ^
misspelling.cpp:54:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     int qry(int l,int r){
      |                        ^
misspelling.cpp:63:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 | int32_t main(){
      |              ^
misspelling.cpp: In function 'void setIO(std::string)':
misspelling.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+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
misspelling.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11