oj.uz

Submission #224141

# Submission time Handle Problem Language Result Execution time Memory
224141 2020-04-17T08:47:34 Z errorgorn Fire (JOI20_ho_t5) C++14
14 / 100
 311 ms 32184 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=start-(start>end);x!=end-(start>end);x+=(start<end?1:-1))
#define all(x) x.begin(),x.end()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a, Args... args) { return max(a,MAX(args...)); }
template<typename... Args>
ll MIN(ll a, Args... args) { return min(a,MIN(args...)); }

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

struct node{
  int s,e,m;
  long long val=-1;
  node *l,*r;
  node(int _s,int _e){
    s=_s,e=_e,m=(s+e)>>1;
    if (s==e){
      val=0; //here the value of all points is 0 at first
    }
    else{
      l=new node(s,m);
      r=new node(m+1,e);
      val=l->val+r->val; //edit this for diff
    }
  }
  long long query(int i,int j){
    if (i==s && j==e) return val;
    else if (j<=m) return l->query(i,j);
    else if (m<i) return r->query(i,j);
    else return max(l->query(i,m),r->query(m+1,j));
  }
  void update(int i, long long k){
    if (s==e){
      val=k;
    }
    else{
        if (i<=m) l->update(i,k);
        else r->update(i,k);
        val=max(l->val,r->val);
    }
  }
}*root=new node(0,200005);

int n,k;
ll arr[200005];
vector<iii> q;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	rep(x,1,n+1){
		cin>>arr[x];
		root->update(x,arr[x]);
	}
	
	bool ST2=true,ST3=true;
		
	int a,b,c;
	rep(x,0,k){
		cin>>a>>b>>c;
		
		if (b!=c) ST3=false;
		
		q.push_back(iii(a,ii(b,c)));
		
		if (q[0].first!=q.back().first) ST2=false;
	}
	
	if (n<=200 && k<=200){
		for (auto &it:q){
			ll ans=0;
			rep(x,it.second.first,it.second.second+1){
				ans+=root->query(max(0LL,x-it.first),x);	
			}
			cout<<ans<<endl;
		}
	}
	else if (ST3){
		for (auto &it:q){
			cout<<root->query(max(0LL,it.second.first-it.first),it.second.first)<<endl;	
		}
	}
	else if (ST2){
		rep(x,1,n+1) arr[x]=root->query(max(0LL,x-q[0].first),x);
		rep(x,1,n+1) arr[x]+=arr[x-1];
		
		for (auto &it:q){
			cout<<arr[it.second.second]-arr[it.second.first-1]<<endl;
		}
	}
}

Compilation message

ho_t5.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
ho_t5.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
ho_t5.cpp:4:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

Subtask #1
1.0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19072 KB Output is correct
2 Correct 188 ms 31432 KB Output is correct
3 Correct 189 ms 31832 KB Output is correct
4 Correct 194 ms 31956 KB Output is correct
5 Correct 191 ms 31832 KB Output is correct
6 Correct 187 ms 31708 KB Output is correct
7 Correct 195 ms 32048 KB Output is correct
8 Correct 190 ms 31960 KB Output is correct
9 Correct 194 ms 31960 KB Output is correct
10 Correct 181 ms 31792 KB Output is correct
11 Correct 187 ms 32132 KB Output is correct
12 Correct 182 ms 31704 KB Output is correct
13 Correct 196 ms 31832 KB Output is correct
14 Correct 197 ms 31704 KB Output is correct
15 Correct 187 ms 32184 KB Output is correct
16 Correct 194 ms 31968 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19072 KB Output is correct
2 Correct 283 ms 30296 KB Output is correct
3 Correct 311 ms 29912 KB Output is correct
4 Correct 281 ms 30168 KB Output is correct
5 Correct 286 ms 29784 KB Output is correct
6 Correct 277 ms 30040 KB Output is correct
7 Correct 288 ms 29888 KB Output is correct
8 Correct 275 ms 30168 KB Output is correct
9 Correct 277 ms 30040 KB Output is correct
10 Correct 267 ms 29912 KB Output is correct
11 Correct 281 ms 30168 KB Output is correct
12 Correct 278 ms 29784 KB Output is correct
13 Correct 276 ms 30168 KB Output is correct
14 Correct 277 ms 29916 KB Output is correct
15 Correct 281 ms 29872 KB Output is correct
16 Correct 279 ms 29784 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 28896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19072 KB Output is correct
2 Correct 24 ms 19200 KB Output is correct
3 Correct 23 ms 19200 KB Output is correct
4 Correct 23 ms 19200 KB Output is correct
5 Correct 25 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 23 ms 19200 KB Output is correct
8 Correct 25 ms 19200 KB Output is correct
9 Correct 24 ms 19200 KB Output is correct
10 Correct 23 ms 19200 KB Output is correct
11 Correct 26 ms 19200 KB Output is correct
12 Correct 23 ms 19200 KB Output is correct
13 Correct 24 ms 19192 KB Output is correct
14 Correct 23 ms 19200 KB Output is correct
15 Correct 23 ms 19200 KB Output is correct
16 Correct 25 ms 19200 KB Output is correct
17 Correct 23 ms 19200 KB Output is correct
18 Correct 23 ms 19200 KB Output is correct
19 Correct 23 ms 19200 KB Output is correct
20 Correct 24 ms 19112 KB Output is correct
21 Correct 23 ms 19200 KB Output is correct
22 Correct 24 ms 19200 KB Output is correct
23 Correct 23 ms 19200 KB Output is correct
24 Correct 24 ms 19200 KB Output is correct
25 Correct 24 ms 19192 KB Output is correct
26 Correct 23 ms 19200 KB Output is correct
27 Correct 23 ms 19200 KB Output is correct
28 Correct 24 ms 19264 KB Output is correct
29 Correct 23 ms 19200 KB Output is correct
30 Correct 24 ms 19200 KB Output is correct
31 Correct 23 ms 19200 KB Output is correct
32 Correct 24 ms 19200 KB Output is correct
33 Incorrect 149 ms 30048 KB Output isn't correct
34 Halted 0 ms 0 KB -