답안 #224140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224140	2020-04-17T08:47:09 Z	errorgorn	Fire (JOI20_ho_t5)	C++14	8 / 100	318 ms	27476 KB

ho_t5

#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;
int 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

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19072 KB	Output is correct
2	Correct	23 ms	19200 KB	Output is correct
3	Correct	24 ms	19192 KB	Output is correct
4	Correct	25 ms	19184 KB	Output is correct
5	Correct	26 ms	19200 KB	Output is correct
6	Correct	23 ms	19200 KB	Output is correct
7	Correct	25 ms	19176 KB	Output is correct
8	Correct	23 ms	19248 KB	Output is correct
9	Correct	23 ms	19192 KB	Output is correct
10	Correct	28 ms	19192 KB	Output is correct
11	Correct	24 ms	19200 KB	Output is correct
12	Correct	22 ms	19200 KB	Output is correct
13	Correct	23 ms	19168 KB	Output is correct
14	Correct	28 ms	19192 KB	Output is correct
15	Correct	23 ms	19200 KB	Output is correct
16	Correct	26 ms	19200 KB	Output is correct
17	Correct	24 ms	19200 KB	Output is correct
18	Correct	26 ms	19200 KB	Output is correct
19	Correct	24 ms	19200 KB	Output is correct
20	Correct	27 ms	19192 KB	Output is correct
21	Correct	25 ms	19112 KB	Output is correct
22	Correct	24 ms	19200 KB	Output is correct
23	Correct	25 ms	19176 KB	Output is correct
24	Correct	24 ms	19200 KB	Output is correct
25	Correct	24 ms	19184 KB	Output is correct
26	Correct	26 ms	19200 KB	Output is correct
27	Correct	24 ms	19200 KB	Output is correct
28	Correct	23 ms	19200 KB	Output is correct
29	Correct	22 ms	19200 KB	Output is correct
30	Correct	24 ms	19200 KB	Output is correct
31	Correct	24 ms	19200 KB	Output is correct
32	Correct	33 ms	19200 KB	Output is correct

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19072 KB	Output is correct
2	Incorrect	193 ms	27476 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19072 KB	Output is correct
2	Correct	318 ms	27300 KB	Output is correct
3	Correct	296 ms	27096 KB	Output is correct
4	Correct	307 ms	27360 KB	Output is correct
5	Correct	302 ms	27040 KB	Output is correct
6	Correct	307 ms	27160 KB	Output is correct
7	Correct	307 ms	27092 KB	Output is correct
8	Correct	317 ms	27352 KB	Output is correct
9	Correct	305 ms	27144 KB	Output is correct
10	Correct	285 ms	26972 KB	Output is correct
11	Correct	298 ms	27328 KB	Output is correct
12	Correct	295 ms	26968 KB	Output is correct
13	Correct	293 ms	27352 KB	Output is correct
14	Correct	296 ms	27224 KB	Output is correct
15	Correct	285 ms	27096 KB	Output is correct
16	Correct	298 ms	26944 KB	Output is correct

Subtask #4
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	129 ms	26592 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19072 KB	Output is correct
2	Correct	23 ms	19200 KB	Output is correct
3	Correct	24 ms	19192 KB	Output is correct
4	Correct	25 ms	19184 KB	Output is correct
5	Correct	26 ms	19200 KB	Output is correct
6	Correct	23 ms	19200 KB	Output is correct
7	Correct	25 ms	19176 KB	Output is correct
8	Correct	23 ms	19248 KB	Output is correct
9	Correct	23 ms	19192 KB	Output is correct
10	Correct	28 ms	19192 KB	Output is correct
11	Correct	24 ms	19200 KB	Output is correct
12	Correct	22 ms	19200 KB	Output is correct
13	Correct	23 ms	19168 KB	Output is correct
14	Correct	28 ms	19192 KB	Output is correct
15	Correct	23 ms	19200 KB	Output is correct
16	Correct	26 ms	19200 KB	Output is correct
17	Correct	24 ms	19200 KB	Output is correct
18	Correct	26 ms	19200 KB	Output is correct
19	Correct	24 ms	19200 KB	Output is correct
20	Correct	27 ms	19192 KB	Output is correct
21	Correct	25 ms	19112 KB	Output is correct
22	Correct	24 ms	19200 KB	Output is correct
23	Correct	25 ms	19176 KB	Output is correct
24	Correct	24 ms	19200 KB	Output is correct
25	Correct	24 ms	19184 KB	Output is correct
26	Correct	26 ms	19200 KB	Output is correct
27	Correct	24 ms	19200 KB	Output is correct
28	Correct	23 ms	19200 KB	Output is correct
29	Correct	22 ms	19200 KB	Output is correct
30	Correct	24 ms	19200 KB	Output is correct
31	Correct	24 ms	19200 KB	Output is correct
32	Correct	33 ms	19200 KB	Output is correct
33	Incorrect	150 ms	26992 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

답안 #224140

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 0 / 6.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 6.0

Subtask #5 0 / 80.0

Subtask #1
1.0 / 1.0

Subtask #2
0 / 6.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 6.0

Subtask #5
0 / 80.0