Submission #1005178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005178		jonathanirvings	Flooding Wall (BOI24_wall)	C++17	37 / 100	5087 ms	20696 KiB

Main

//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s);
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s);
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

template <int Mod>
struct ModInt {
  
  ModInt() : num_(0) {}
 
  template <class T>
  ModInt(T num) {
    long long x = (long long)(num % (long long)(Mod));
    if (x < 0) x += Mod;
    num_ = (int)(x);
  }
 
  ModInt& operator++() {
    num_++;
    if (num_ == Mod) num_ = 0;
    return *this;
  }
  ModInt& operator--() {
    if (num_ == 0) num_ = Mod;
    num_--;
    return *this;
  }
  ModInt operator++(int) {
    ModInt result = *this;
    ++*this;
    return result;
  }
  ModInt operator--(int) {
    ModInt result = *this;
    --*this;
    return result;
  }
 
  ModInt& operator+=(const ModInt& rhs) {
    num_ += rhs.num_;
    if (num_ >= Mod) num_ -= Mod;
    return *this;
  }
  ModInt& operator-=(const ModInt& rhs) {
    num_ -= rhs.num_;
    if (num_ < 0) num_ += Mod;
    return *this;
  }
  ModInt& operator*=(const ModInt& rhs) {
    long long z = num_;
    z *= rhs.num_;
    num_ = (int)(z % Mod);
    return *this;
  }
  ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); }
 
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return ModInt() - *this; }
 
  ModInt pow(long long n) const {
    assert(0 <= n);
    ModInt x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  ModInt inv() const {
    return pow(Mod - 2);
  }
 
  friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) += rhs;
  }
  friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) -= rhs;
  }
  friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) *= rhs;
  }
  friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) /= rhs;
  }
  friend bool operator==(const ModInt& lhs, const ModInt& rhs) {
    return lhs.num_ == rhs.num_;
  }
  friend bool operator!=(const ModInt& lhs, const ModInt& rhs) {
    return lhs.num_ != rhs.num_;
  }
 
  int get() const { return num_; }
 
  int num_;
};
 
template <int Mod>
struct ModBinomCoeff {
 
  ModBinomCoeff() {}
  ModBinomCoeff(int N) : fact_(N + 1), inv_fact_(N + 1) {
    fact_[0] = 1;
    for (int i = 1; i <= N; ++i) {
      fact_[i] = fact_[i - 1] * (i);
    }
    inv_fact_[N] = fact_[N].inv();
    for (int i = N - 1; i >= 0; --i) {
      inv_fact_[i] = inv_fact_[i + 1] * (i + 1);
    }
  }
 
  ModInt<Mod> fact(int N) {
    assert(N < fact_.size());
    return fact_[N];
  }
  ModInt<Mod> choose(int N, int K) {
    assert(N < fact_.size());
    return fact_[N] * inv_fact_[K] * inv_fact_[N - K];
  }
 
  vector<ModInt<Mod>> fact_;
  vector<ModInt<Mod>> inv_fact_;
};
 
constexpr int Mod998244353 = 998244353;
constexpr int Mod1000000007 = 1000000007;
constexpr int Mod = Mod1000000007;

using Int = ModInt<Mod>;

int n;
int a[500005];
int b[500005];
int rem[500005];
Int totkiri[500005],totkanan[500005];

int main()
{
  scanf("%d",&n);
  REP(i,n) scanf("%d",&a[i]);
  REP(i,n) scanf("%d",&b[i]);
  vii angka;
  REP(i,n)
  {
    angka.pb(mp(a[i],i));
    angka.pb(mp(b[i],i));
  }
  SORT(angka);
  Int risan = 0;
  if (angka.back().fi == 2)
  {
    Int kiri = 1;
    Int kanan = Int(2).pow(n - 1);
    REP(i,n)
    {
      risan += (kiri - 1) * (kanan - 1);
      kiri *= 2;
      kanan /= 2;
    }
    printf("%d\n",risan.get());
    return 0;
  }
  REP(i,n) rem[i] = 2;
  FORD(i,SIZE(angka)-1,0)
  {
    int pos = angka[i].se;
    int h = angka[i].fi;
    totkiri[0] = 1;
    FOR(j,1,n) totkiri[j] = totkiri[j - 1] * rem[j - 1];
    totkanan[n - 1] = 1;
    FORD(j,n-2,0) totkanan[j] = totkanan[j + 1] * rem[j + 1];
    
    {
      Int cur = 1;
      FOR(j,0,pos) cur *= rem[j];
      FOR(j,pos+1,n)
      {
        // risan += cur * h * totkanan[j] * rem[j];
        // totkiri[j] += cur;
        risan += cur * h * rem[j] * (Int(2).pow(n - j - 1) - totkanan[j]);
        cur *= rem[j];
      }
    }
    {
      Int cur = 1;
      FORD(j,n-1,pos+1) cur *= rem[j];
      FORD(j,pos-1,0)
      {
        // risan += cur * h * totkiri[j] * rem[j];
        // totkanan[j] += cur;
        risan += cur * h * rem[j] * (Int(2).pow(j) - totkiri[j]);
        cur *= rem[j];
      }
    }
    {
      // Int cur = 1;
      // REP(j,n) if (j != pos) cur *= rem[j];
      // risan += h * cur;
      // cur = 1;
      // REP(j,pos) cur *= rem[j];
      // risan += h * cur * totkanan[pos];
      // cur = 1;
      // FORD(j,n-1,pos+1) cur *= rem[j];
      // risan += h * cur * totkiri[pos];
      risan += h * totkiri[pos] * Int(2).pow(n - pos - 1);
      risan += h * Int(2).pow(pos) * totkanan[pos];
      risan -= h * totkiri[pos] * totkanan[pos];
    }
    --rem[pos];
  }
  REP(i,n) risan -= (a[i] + b[i]) * Int(2).pow(n - 1);
  printf("%d\n",risan.get());
}

Compilation message (stderr)

Main.cpp: In function 'std::string uppercase(std::string)':
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:79:3: note: in expansion of macro 'REP'
   79 |   REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
Main.cpp: In function 'std::string lowercase(std::string)':
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:85:3: note: in expansion of macro 'REP'
   85 |   REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
Main.cpp: In function 'int main()':
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:233:3: note: in expansion of macro 'REP'
  233 |   REP(i,n) scanf("%d",&a[i]);
      |   ^~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:234:3: note: in expansion of macro 'REP'
  234 |   REP(i,n) scanf("%d",&b[i]);
      |   ^~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:236:3: note: in expansion of macro 'REP'
  236 |   REP(i,n)
      |   ^~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:247:5: note: in expansion of macro 'REP'
  247 |     REP(i,n)
      |     ^~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:256:3: note: in expansion of macro 'REP'
  256 |   REP(i,n) rem[i] = 2;
      |   ^~~
Main.cpp:35:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
      |                              ^
Main.cpp:257:3: note: in expansion of macro 'FORD'
  257 |   FORD(i,SIZE(angka)-1,0)
      |   ^~~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:262:5: note: in expansion of macro 'FOR'
  262 |     FOR(j,1,n) totkiri[j] = totkiri[j - 1] * rem[j - 1];
      |     ^~~
Main.cpp:35:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
      |                              ^
Main.cpp:264:5: note: in expansion of macro 'FORD'
  264 |     FORD(j,n-2,0) totkanan[j] = totkanan[j + 1] * rem[j + 1];
      |     ^~~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:268:7: note: in expansion of macro 'FOR'
  268 |       FOR(j,0,pos) cur *= rem[j];
      |       ^~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:269:7: note: in expansion of macro 'FOR'
  269 |       FOR(j,pos+1,n)
      |       ^~~
Main.cpp:35:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
      |                              ^
Main.cpp:279:7: note: in expansion of macro 'FORD'
  279 |       FORD(j,n-1,pos+1) cur *= rem[j];
      |       ^~~~
Main.cpp:35:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
      |                              ^
Main.cpp:280:7: note: in expansion of macro 'FORD'
  280 |       FORD(j,pos-1,0)
      |       ^~~~
Main.cpp:33:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
      |                             ^
Main.cpp:39:18: note: in expansion of macro 'FOR'
   39 | #define REP(i,n) FOR(i,0,n)
      |                  ^~~
Main.cpp:304:3: note: in expansion of macro 'REP'
  304 |   REP(i,n) risan -= (a[i] + b[i]) * Int(2).pow(n - 1);
      |   ^~~
Main.cpp:232:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
Main.cpp:233:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |   REP(i,n) scanf("%d",&a[i]);
      |            ~~~~~^~~~~~~~~~~~
Main.cpp:234:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |   REP(i,n) scanf("%d",&b[i]);
      |            ~~~~~^~~~~~~~~~~~

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