oj.uz

Submission #1119644

# Submission time Handle Problem Language Result Execution time Memory
1119644 2024-11-27T09:05:27 Z squatrian Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 149 ms 5568 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using std::mt19937_64;
using std::random_device;
using std::uniform_int_distribution;
#include <numeric>
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("art2.in", "r", stdin);
    freopen("art2.out", "w", stdout);
#endif
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int exp(int x, int n, int m) {
    if(x == 0 and n == 0) return 1;
    x %= m; 
    int res = 1;
    while (n > 0) {
        if (n % 2 == 1) { res = res * x % m; }
        x = x * x % m;
        n /= 2;
    }
    return res;
}
int modinv(int n) {
    int r = 1;
    int p = mod - 2;
    while (p > 0) {
        if (p % 2 == 1) {
            r = (r * n) % mod;
        }
        n = (n * n) % mod;
        p /= 2;
    }
    return r;
}
int mul(int a,int b){
    return ((a*b)%mod);
}
int val(int a){
    return ((((a*(a+1))%mod)*modinv(2))%mod);
}
signed main()
{   
   int t=1;
   // c_p_c();
   // cin >> t;
   while(t--){
   int n;
   cin >> n;
   vector<int> h(n+1),w(n+1);
   for(int i = 1 ; i <= n; i++) cin >> h[i];
   for(int i = 1 ; i <= n; i++) cin >> w[i];
   stack<pair<int,int>> s;
   int ans = 0;
   for(int i = 1 ; i <= n; i++){
    if(s.empty() or s.top().ff <= h[i]){
        if(!s.empty() and s.top().ff == h[i]){
            s.top().ss = (w[i]+s.top().ss)%mod;
        }
        else{
            s.push({h[i],w[i]});
        }
    }
    else{
        int width = 0;
      while(!s.empty() and s.top().ff > h[i]){
        ans = (ans + mul(val(s.top().ff),val(width+s.top().ss)))%mod;
        ans = (ans - mul(val(s.top().ff),val(width))+mod)%mod;
        width = (width+s.top().ss)%mod;
        s.pop();
      }
      ans = (ans - mul(val(h[i]),val(width)+mod))%mod;
      if(!s.empty() and s.top().ff == h[i]){
            s.top().ss = (s.top().ss+(w[i]+width))%mod;
        }
        else{
            s.push({h[i],(w[i]+width)%mod});
        }
    }
    // cout<<ans<<endl;
   }
   int width = 0;
      while(!s.empty()){
        ans = (ans + mul(val(s.top().ff),val(width+s.top().ss)))%mod;
        ans = (ans - mul(val(s.top().ff),val(width))+mod)%mod;
        width = (width+s.top().ss)%mod;
        s.pop();
      }
      cout<<ans<<endl;

 
   }
    return 0;
}

Compilation message

fancyfence.cpp: In function 'void c_p_c()':
fancyfence.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen("art2.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fancyfence.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("art2.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 36 ms 1596 KB Output is correct
4 Correct 69 ms 3012 KB Output is correct
5 Correct 58 ms 3152 KB Output is correct
6 Correct 50 ms 3148 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 7 ms 796 KB Output is correct
3 Correct 30 ms 2096 KB Output is correct
4 Correct 67 ms 3784 KB Output is correct
5 Correct 62 ms 3904 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 10 ms 592 KB Output is correct
4 Correct 45 ms 2096 KB Output is correct
5 Correct 72 ms 3908 KB Output is correct
6 Correct 60 ms 3908 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 13 ms 708 KB Output is correct
9 Correct 39 ms 2564 KB Output is correct
10 Correct 122 ms 5448 KB Output is correct
11 Correct 113 ms 5568 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 508 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 456 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 27 ms 1616 KB Output is correct
12 Correct 48 ms 3164 KB Output is correct
13 Correct 53 ms 3164 KB Output is correct
14 Correct 55 ms 3104 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 10 ms 792 KB Output is correct
17 Correct 29 ms 2100 KB Output is correct
18 Correct 69 ms 3908 KB Output is correct
19 Correct 53 ms 3912 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 11 ms 964 KB Output is correct
22 Correct 38 ms 2376 KB Output is correct
23 Correct 101 ms 5324 KB Output is correct
24 Correct 121 ms 5560 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 2 ms 336 KB Output is correct
30 Correct 14 ms 792 KB Output is correct
31 Correct 16 ms 788 KB Output is correct
32 Correct 55 ms 1844 KB Output is correct
33 Correct 65 ms 2128 KB Output is correct
34 Correct 119 ms 3664 KB Output is correct
35 Correct 135 ms 3656 KB Output is correct
36 Correct 139 ms 3780 KB Output is correct
37 Correct 139 ms 3912 KB Output is correct
38 Correct 1 ms 512 KB Output is correct
39 Correct 148 ms 3904 KB Output is correct
40 Correct 123 ms 3928 KB Output is correct
41 Correct 121 ms 3948 KB Output is correct
42 Correct 149 ms 4676 KB Output is correct