oj.uz

Submission #991497

# Submission time Handle Problem Language Result Execution time Memory
991497 2024-06-02T10:39:00 Z modwwe Fire (JOI20_ho_t5) C++17
1 / 100
 88 ms 60872 KB 
#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[200001];
vector<ic> v3[200001];
int ans[200001];
int a[200001];
int b[200001];
int c[200001];
int o;
struct IT
{
     int t[2000001],lazy[2000001],sz[2000001];
     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);
          }
         for(auto x:v3[i]){
         st2.upd(x.a,x.b,x.c);
         }
         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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28248 KB Output is correct
2 Correct 5 ms 26460 KB Output is correct
3 Correct 5 ms 26460 KB Output is correct
4 Correct 5 ms 26460 KB Output is correct
5 Correct 5 ms 26460 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 5 ms 26300 KB Output is correct
8 Correct 5 ms 26712 KB Output is correct
9 Correct 5 ms 26460 KB Output is correct
10 Correct 5 ms 26460 KB Output is correct
11 Correct 5 ms 26460 KB Output is correct
12 Correct 7 ms 26460 KB Output is correct
13 Correct 5 ms 26460 KB Output is correct
14 Correct 5 ms 26460 KB Output is correct
15 Correct 5 ms 26460 KB Output is correct
16 Correct 5 ms 26460 KB Output is correct
17 Correct 5 ms 26460 KB Output is correct
18 Correct 5 ms 26460 KB Output is correct
19 Correct 5 ms 26460 KB Output is correct
20 Correct 5 ms 26460 KB Output is correct
21 Correct 5 ms 26460 KB Output is correct
22 Correct 5 ms 26460 KB Output is correct
23 Correct 6 ms 26460 KB Output is correct
24 Correct 5 ms 26456 KB Output is correct
25 Correct 5 ms 26344 KB Output is correct
26 Correct 5 ms 26460 KB Output is correct
27 Correct 5 ms 26460 KB Output is correct
28 Correct 5 ms 26460 KB Output is correct
29 Correct 6 ms 26456 KB Output is correct
30 Correct 6 ms 26460 KB Output is correct
31 Correct 5 ms 26460 KB Output is correct
32 Correct 5 ms 26460 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28248 KB Output is correct
2 Runtime error 69 ms 58036 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28248 KB Output is correct
2 Runtime error 88 ms 60872 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 58976 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28248 KB Output is correct
2 Correct 5 ms 26460 KB Output is correct
3 Correct 5 ms 26460 KB Output is correct
4 Correct 5 ms 26460 KB Output is correct
5 Correct 5 ms 26460 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 5 ms 26300 KB Output is correct
8 Correct 5 ms 26712 KB Output is correct
9 Correct 5 ms 26460 KB Output is correct
10 Correct 5 ms 26460 KB Output is correct
11 Correct 5 ms 26460 KB Output is correct
12 Correct 7 ms 26460 KB Output is correct
13 Correct 5 ms 26460 KB Output is correct
14 Correct 5 ms 26460 KB Output is correct
15 Correct 5 ms 26460 KB Output is correct
16 Correct 5 ms 26460 KB Output is correct
17 Correct 5 ms 26460 KB Output is correct
18 Correct 5 ms 26460 KB Output is correct
19 Correct 5 ms 26460 KB Output is correct
20 Correct 5 ms 26460 KB Output is correct
21 Correct 5 ms 26460 KB Output is correct
22 Correct 5 ms 26460 KB Output is correct
23 Correct 6 ms 26460 KB Output is correct
24 Correct 5 ms 26456 KB Output is correct
25 Correct 5 ms 26344 KB Output is correct
26 Correct 5 ms 26460 KB Output is correct
27 Correct 5 ms 26460 KB Output is correct
28 Correct 5 ms 26460 KB Output is correct
29 Correct 6 ms 26456 KB Output is correct
30 Correct 6 ms 26460 KB Output is correct
31 Correct 5 ms 26460 KB Output is correct
32 Correct 5 ms 26460 KB Output is correct
33 Runtime error 69 ms 58036 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -