Submission #498637

#TimeUsernameProblemLanguageResultExecution timeMemory
498637RambaXGorillaFancy Fence (CEOI20_fancyfence)C++17
100 / 100
38 ms5208 KiB
#include<cstdio> #include<algorithm> #include<utility> #include<queue> using namespace std; typedef long long ll; typedef pair <int,int> ii; #define pq priority_queue const int modNum = 1000000007; int N; int heights[100010]; int widths[100010]; ll prefs[100010]; int smaller[100010]; pq <ii> big; int form(ll a, ll b){ ll nums[] = {a, b, a + 1, b + 1}; for(int i = 0;i < 4;i++){ if(!(nums[i] % 2)){ nums[i] /= 2; } nums[i] %= modNum; } ll prod = 1; for(int i = 0;i < 4;i++){ prod *= nums[i]; prod %= modNum; } return prod; } int main(){ scanf("%d",&N); for(int i = 0;i < N;i++){ scanf("%d",&heights[i]); } heights[N] = 0; prefs[0] = 0; for(int i = 0;i < N;i++){ scanf("%d",&widths[i]); prefs[i + 1] = prefs[i] + widths[i]; } for(int i = 0;i < N + 1;i++){ while(!big.empty() && big.top().first > heights[i]){ smaller[big.top().second] = i; big.pop(); } big.push(ii(heights[i], i)); } int total = 0; for(int i = 0;i < N;i++){ int bott = 0; if(i > 0){ bott = heights[i - 1]; } int curr = i; int last; while(curr < N){ last = curr; curr = smaller[curr]; if(heights[last] <= bott){ break; } total += (form(heights[last], prefs[curr] - prefs[i]) - form(max(heights[curr], bott), prefs[curr] - prefs[i]) + modNum) % modNum; total %= modNum; } } printf("%d",total); }

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
fancyfence.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d",&heights[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
fancyfence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d",&widths[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...