Submission #1043634

#TimeUsernameProblemLanguageResultExecution timeMemory
1043634YassineBenYounesFlooding Wall (BOI24_wall)C++17
25 / 100
358 ms468 KiB
#include<bits/stdc++.h> //#include<chrono> //#include<random> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1}; int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1}; #define endl "\n" #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pbds tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update> using namespace __gnu_pbds; using namespace std; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ////////////////////Only Clear Code////////////////////////// void usaco_problem(){ freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout); } void init(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE } const int mx = 105; const int LOG = 22; const int inf = 1e9; const ll mod = 1e9+7; const int sq = 320; int n; ll a[mx], b[mx]; ////0//////1////// int32_t main(){ speed; cin >> n; for(int i = 0; i < n;i++){ cin >> a[i]; } for(int i = 0; i < n;i++){ cin >> b[i]; if(a[i] > b[i])swap(a[i], b[i]); } ll ans = 0; for(int i = 1; i < n-1;i++){ set<ll> s; vl v1; ll mn = -1; for(int j = 0;j < i;j++){ s.insert(a[j]); s.insert(b[j]); v1.pb(max(a[j], b[j])); mn = max(mn, min(a[j], b[j])); //v1.pb({a[j], j, 0}); //v1.pb({b[j], j, 1}); } sort(all(v1), greater<ll>()); set<ll> s1; for(int j = i+1;j < n;j++){ s1.insert(a[j]); s1.insert(b[j]); //v1.pb({a[j], j, 0}); //v1.pb({b[j], j, 1}); } ll last1 = 0; ll gposs1 = 1; for(ll x : s){ while(v1.size() > 0 && v1.back() <= x){ gposs1 *= 2; gposs1 %= mod; v1.pop_back(); } ll poss1 = gposs1; if(mn > x)poss1 = 0; //cout << i << " " << x << " " << poss1 << endl; /*for(int k = 0;k < i;k++){ if(max(a[k], b[k]) <= x){ poss1 *= 2; poss1 %= mod; } if(min(a[k], b[k]) > x){ poss1 = 0; } }*/ ll cur1 = poss1-last1; cur1 %= mod; while(cur1 < 0)cur1 += mod; last1 = poss1; ll last2 = 0; for(ll y : s1){ ll poss2 = 1; for(int k = i+1;k < n;k++){ if(max(a[k], b[k]) <= y){ poss2 *= 2; poss2 %= mod; } if(min(a[k], b[k]) > y){ poss2 = 0; } } ll cur2 = poss2 - last2; cur2 %= mod; while(cur2 < 0)cur2 += mod; ll p = (cur1*cur2) % mod; ans += (max(0LL, min(x, y) - a[i]) * p) % mod; ans %= mod; ans += (max(0LL, min(x, y) - b[i]) * p) % mod; ans %= mod; last2 = poss2; } } } cout << ans << endl; } /* NEVER GIVE UP! DOING SMTHNG IS BETTER THAN DOING NTHNG!!! Your Guide when stuck: - Continue keyword only after reading the whole input - Don't use memset with testcases - Check for corner cases(n=1, n=0) - Check where you declare n(Be careful of declaring it globally and in main) */

Compilation message (stderr)

Main.cpp: In function 'void usaco_problem()':
Main.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void init()':
Main.cpp:43:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...