제출 #1107070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1107070		vjudge1	Flooding Wall (BOI24_wall)	C++17	8 / 100	119 ms	6992 KiB

Main

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int mod=1e9+7;
const int M=5e5+10;
int n,a[M],b[M];
namespace sub1
{
  const int M=30;
  int x[M],y[M],kq=0;
  void ktra()
  {
    fori(i,1,n) y[i]=1e9;
    int l=0,r=0;
    fori(i,1,n) {
      l=max(l,x[i]);
      y[i]=min(y[i],l);
    }
    for(int i=n;i!=0;i--) {
      r=max(r,x[i]);
      y[i]=min(y[i],r);
    }
    fori(i,1,n) kq=(kq+max(0ll,y[i]-x[i]))%mod;
  }
  void duyet(int i)
  {
    if(i==n+1) ktra();
    else {
      fori(j,0,1) {
        if(j) x[i]=a[i];
        else x[i]=b[i];
        duyet(i+1);
      }
    }
  }
  void solve()
  {
    duyet(1);
    cout << kq ;
  }
}

namespace sub3
{
  const int M=1e4+10;
  const int N=2e4+10;
  int f[M][N],g[2][N],kq=0;
  vector<int>  rrh;
  void solve()
  {
    fori(i,1,n) {
      rrh.pb(a[i]);
      rrh.pb(b[i]);
    }
    sort(rrh.begin(),rrh.end());
    rrh.resize(unique(rrh.begin(),rrh.end())-rrh.begin());
    fori(i,1,n) {
      a[i]=lower_bound(rrh.begin(),rrh.end(),a[i])-rrh.begin();
      b[i]=lower_bound(rrh.begin(),rrh.end(),b[i])-rrh.begin();
    }
    int lim=rrh.size();


    g[n+1][0]=1;
    for(int i=n;i!=0;i--) {
      fori(j,0,lim) {
        int val=max(a[i],j);
        int val2=max(b[i],j);
        g[i][val]=(g[i+1][j]+g[i][val])%mod;
        g[i][val2]=(g[i+1][j]+g[i][val2])%mod;
      }
    }
    f[0][0]=1;
    fori(i,1,n) {
      fori(j,0,lim) {
        int val=max(a[i],j);
        int val2=max(b[i],j);
        f[i&1][val]=(f[i-1&1][j]+f[i&1][val])%mod;
        f[i&1][val2]=(f[i-1&1][j]+f[i&1][val2])%mod;
      }

        int sum=0;
        for(int j=lim;j>=min(a[i],b[i]);j--) {
          sum=(sum+g[i+1][j])%mod;
          if(a[i]<=j) kq=(kq+(f[i-1&1][j]*sum)%mod*(rrh[j]-rrh[a[i]])%mod)%mod;
          if(b[i]<=j) kq=(kq+(f[i-1&1][j]*sum)%mod*(rrh[j]-rrh[b[i]])%mod)%mod;
      }
        sum=0;
        for(int j=lim;j>=min(a[i],b[i]);j--) {
        if(a[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(rrh[j]-rrh[a[i]])%mod)%mod;
        if(b[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(rrh[j]-rrh[b[i]])%mod)%mod;
        sum=(sum+f[i-1&1][j])%mod;
      }

      fori(j,0,lim) f[i-1&1][j]=0;
    }

    cout << kq;
  }
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n;
  fori(i,1,n) cin >> a[i];
  fori(i,1,n) cin >> b[i];
  if(n<=20) sub1::solve();
  else sub3::solve();
  //sub3::solve();
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void sub3::solve()':
Main.cpp:83:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   83 |         f[i&1][val]=(f[i-1&1][j]+f[i&1][val])%mod;
      |                        ~^~
Main.cpp:84:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   84 |         f[i&1][val2]=(f[i-1&1][j]+f[i&1][val2])%mod;
      |                         ~^~
Main.cpp:90:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   90 |           if(a[i]<=j) kq=(kq+(f[i-1&1][j]*sum)%mod*(rrh[j]-rrh[a[i]])%mod)%mod;
      |                                 ~^~
Main.cpp:91:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   91 |           if(b[i]<=j) kq=(kq+(f[i-1&1][j]*sum)%mod*(rrh[j]-rrh[b[i]])%mod)%mod;
      |                                 ~^~
Main.cpp:97:21: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   97 |         sum=(sum+f[i-1&1][j])%mod;
      |                    ~^~
Main.cpp:100:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  100 |       fori(j,0,lim) f[i-1&1][j]=0;
      |                       ~^~
Main.cpp: In function 'int32_t main()':
Main.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:119:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void sub3::solve()':
Main.cpp:95:38: warning: array subscript 2 is above array bounds of 'long long int [2][20010]' [-Warray-bounds]
   95 |         if(a[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(rrh[j]-rrh[a[i]])%mod)%mod;
      |                                 ~~~~~^
Main.cpp:52:15: note: while referencing 'sub3::g'
   52 |   int f[M][N],g[2][N],kq=0;
      |               ^
Main.cpp:96:38: warning: array subscript 2 is above array bounds of 'long long int [2][20010]' [-Warray-bounds]
   96 |         if(b[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(rrh[j]-rrh[b[i]])%mod)%mod;
      |                                 ~~~~~^
Main.cpp:52:15: note: while referencing 'sub3::g'
   52 |   int f[M][N],g[2][N],kq=0;
      |               ^
Main.cpp:89:25: warning: array subscript 2 is above array bounds of 'long long int [2][20010]' [-Warray-bounds]
   89 |           sum=(sum+g[i+1][j])%mod;
      |                    ~~~~~^
Main.cpp:52:15: note: while referencing 'sub3::g'
   52 |   int f[M][N],g[2][N],kq=0;
      |               ^

• Subtask 1: 8 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30