/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 141ms 122.766 MiB
#2 Accepted 158ms 122.895 MiB
#3 Accepted 563ms 124.164 MiB
#4 Accepted 1477ms 149.18 MiB
#5 Memory Exceeded ≥691ms ≥256.016 MiB
#6 Memory Exceeded ≥684ms ≥256.016 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 2e5 + 3, mod = 1e9 + 7;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
ordered_set tr[mxn * 4], rt[mxn * 4];
//vector<int> tre[mxn * 4], rtre[mxn * 4];
int ar[mxn];
void build(int st, int ed, int node)
{
//    for(int i = st; i <= ed; i++)tre[node].push_back(ar[i]), rtre[node].push_back(-ar[i]);
//    sort(tre[node].begin(), tre[node].end());
//    sort(rtre[node].begin(), rtre[node].end());
    for(int i = st; i <= ed; i++)tr[node].insert(ar[i]), rt[node].insert(-ar[i]);
    if(st == ed)return;
    int mid = st + ed >> 1;
    build(st, mid, node * 2);
    build(mid + 1, ed, node * 2 + 1);
}

int query(int st, int ed, int node, int l, int r, int x)
{
    if(st > r or ed < l)return 0;
    if(st >= l and ed <= r)
    {
//        auto it = lower_bound(tre[node].begin(), tre[node].end(), x) - tre[node].begin();
//        return it;
         return tr[node].order_of_key(x);
    }
    int mid = st + ed >> 1;
    return query(st, mid, node * 2, l, r, x) + query(mid + 1, ed, node * 2 + 1, l, r, x);
}
int rquery(int st, int ed, int node, int l, int r, int x)
{
    if(st > r or ed < l)return 0;
    if(st >= l and ed <= r)
    {
//       auto it = lower_bound(rtre[node].begin(), rtre[node].end(), -x) - rtre[node].begin();
//       return it;
         return rt[node].order_of_key(-x);
    }
    int mid = st + ed >> 1;
    return rquery(st, mid, node * 2, l, r, x) + rquery(mid + 1, ed, node * 2 + 1, l, r, x);
}
void refresh(int n)
{
    //for(int i = 1; i <= n; i++)tre[i].clear(), rtre[i].clear();
    for(int i = 1; i <= n; i++)tr[i].clear(), rt[i].clear();
}
int32_t main()
{
   fast
   w(t)
   {
       int n;
       cin >> n;
       refresh(n * 4);
       for(int i = 1; i <= n; i++)cin >> ar[i];
       build(1, n, 1);
       int q;
       cin >> q;
       while(q--)
       {
           int l, x, r;
           cin >> l >> x >> r;
           int a = query(1, n, 1, l, x, ar[x]), b = rquery(1, n, 1, x, r, ar[x]);
           int64_t ans = 1LL * a * b;
           a = rquery(1, n, 1, l, x, ar[x]), b = query(1, n, 1, x, r, ar[x]);
           ans += 1LL * a * b;
           cout << ans << endl;

       }
   }
}

Information

Submit By
Type
Submission
Problem
P1082 Roy and Query (Hard Version)
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-12 12:21:07
Judged At
2024-11-12 12:21:07
Judged By
Score
10
Total Time
≥1477ms
Peak Memory
≥256.016 MiB