Submission #991511

#	Time	Username	Problem	Language	Result	Execution time	Memory
991511		modwwe	Fire (JOI20_ho_t5)	C++17	100 / 100	484 ms	148956 KiB

ho_t5

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
///#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int mod2=998244353;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;
 
};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    /// modwwe
    phongbeo();
}
vector<ic> v[200001];
vector<ic> v2[400001];
vector<ic> v3[400001];
int ans[200001];
int a[200001];
int b[200001];
int c[200001];
int o;
struct IT
{
     int t[1600009],lazy[1600009],sz[1600009];
     void ff(int x)
     {
         for(int i=x*2;i<=x*2+1;i++)
            t[i]+=lazy[x]*sz[i],
            lazy[i]+=lazy[x];
 lazy[x]=0;
     }
     void build(int node,int l,int r)
     { sz[node]=r-l+1;
         if(l==r){return;}
     int mid=l+r>>1;
      build(node<<1,l,mid);
       build(node<<1|1,mid+1,r);
     }
     void update(int node,int l,int r,int l1,int r1,int f)
     {
          if(l>r1||r<l1) return ;
          if(l>=l1&&r<=r1)
          {
               t[node]+=f*sz[node];
               lazy[node]+=f;
                return;
          }
          ff(node);
           int mid=l+r>>1;
            update(node<<1,l,mid,l1,r1,f);
            update(node<<1|1,mid+1,r,l1,r1,f);
            t[node]=t[node<<1]+t[node<<1|1];
     }
     int gett(int node,int l,int r,int l1,int r1)
       {
            if(l>r1||r<l1) return 0;
             if(l>=l1&&r<=r1) return t[node];
              ff(node);
              int mid=l+r>>1;
                return gett(node<<1,l,mid,l1,r1)+gett(node<<1|1,mid+1,r,l1,r1);
       }
       void upd(int l,int r,int f)
       {
            l+=o;
             r+=o;
             update(1,0,o+o,l,r,f);
       }
       int get(int l,int r)
       {
        l+=o;
        r+=o;
        return gett(1,0,o+o,l,r);
       }
}st1,st2;
void cf(int x,int y,int z)
{
 v2[0].pb({-o,y,a[y]});
 v3[0].pb({-o,y-1,-a[y]});
 s2=y-1-x;
 v2[s2].pb({-o,x,-a[y]});
 v3[s2].pb({-o,y-1,a[y]});
 s3=z-1-y;
v2[s3].pb({-o,y,-a[y]});
 v3[s3].pb({-o,z-1,a[y]});
s4=z-1-x;
v2[s4].pb({-o,x,a[y]});
v3[s4].pb({-o,z-1,-a[y]});
}
void phongbeo()
{
    cin>>n>>m;
    o=n;
     for(int i=1;i<=n;i++)
          cin>>a[i];
     for(int i=1;i<=m;i++)
     {
           cin>>s2>>s3>>s4;
            v[s2].pb({s3,s4,i});
     }
      vector<int> stk;
	for(int i=n;i>=1;i--) {
		while(!stk.empty() && a[stk.back()]<=a[i]) stk.pop_back();
		if(stk.size()) {
			c[i]=stk.back();
		} else {
			c[i]=n+1;
		}
		stk.push_back(i);
	}
 
	stk.clear();
 
	for(int i=1;i<=n;i++) {
		while(!stk.empty() && a[stk.back()]<a[i]) stk.pop_back();
		if(stk.size()) {
			b[i]=stk.back();
		} else {
			b[i]=-o;
		}
		stk.push_back(i);
	}
	for(int i=1;i<=n;i++)
    { //cout<<b[i]<<" "<<i<<" "<<c[i],down
         cf(b[i],i,c[i]);
    }
    st1.build(1,0,o+o);
    st2.build(1,0,o+o);
    for(int i=0;i<=n;i++)
    {
         for(auto x:v2[i]){
          st1.upd(x.a,x.b,x.c);
         /// if(i==0)
           ///  cout<<x.a<<" "<<x.b<<" "<<x.c<<" goku",down
          }
         for(auto x:v3[i]){
         st2.upd(x.a,x.b,x.c);
              ///   if(i==0)
             ///cout<<x.a<<" "<<x.b<<" "<<x.c<<" cuto",down
         }
         for(auto x:v[i])
            ans[x.c]=st1.get(x.a-i,x.b-i)+st2.get(x.a,x.b);
    }
    for(int i=1;i<=m;i++)
    {
      cout<<ans[i],down
    }
 
}

Compilation message (stderr)

ho_t5.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
ho_t5.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
ho_t5.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |      int mid=l+r>>1;
      |              ~^~
ho_t5.cpp: In member function 'void IT::update(long long int, long long int, long long int, long long int, long long int, long long int)':
ho_t5.cpp:90:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |            int mid=l+r>>1;
      |                    ~^~
ho_t5.cpp: In member function 'long long int IT::gett(long long int, long long int, long long int, long long int, long long int)':
ho_t5.cpp:100:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |               int mid=l+r>>1;
      |                       ~^~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80