oj.uz

Submission #224160

# Submission time Handle Problem Language Result Execution time Memory
224160 2020-04-17T08:58:59 Z errorgorn Fire (JOI20_ho_t5) C++14
20 / 100
 669 ms 80344 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);

struct node2{
  int s,e,m;
  vector<int> val;
  node2 *l,*r;
  node2(int _s,int _e){
    s=_s,e=_e,m=(s+e)>>1;
    if (s!=e){
      l=new node2(s,m);
      r=new node2(m+1,e);
    }
  }
  long long query(int i,int j,int k){
    if (i==s && j==e){
		return distance(val.begin(),upper_bound(all(val),k));
	}
    else if (j<=m) return l->query(i,j,k);
    else if (m<i) return r->query(i,j,k);
    else return l->query(i,m,k)+r->query(m+1,j,k);
  }
  void update(int i, long long k){
    val.push_back(k);
	
	if (s==e) return;
    else if (i<=m) l->update(i,k);
   	else r->update(i,k);
  }

	void ss(){
		sort(all(val));
		
		if (s!=e){
			l->ss();
			r->ss();
		}
	}
}*root2=new node2(0,200005);

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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	bool ST2=true,ST3=true,ST4=true;
	
	cin>>n>>k;
	rep(x,1,n+1){
		cin>>arr[x];
		if (arr[x]>2) ST4=false;
		root->update(x,arr[x]);
	}
		
	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 (ST4){
		int p=1000000000;
		
		rep(x,1,n+1){
			if (arr[x]==2) p=0;
			else p++;
			root2->update(x,p);
		}
		root2->ss();
		
		for (auto &it:q){
			int twos=root2->query(it.second.first,it.second.second,it.first);
			cout<<it.second.second-it.second.first+1+twos<<endl;
		}
		
	}
	else 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 41 ms 44160 KB Output is correct
2 Correct 44 ms 44152 KB Output is correct
3 Correct 45 ms 44152 KB Output is correct
4 Correct 43 ms 44152 KB Output is correct
5 Correct 42 ms 44152 KB Output is correct
6 Correct 42 ms 44152 KB Output is correct
7 Correct 43 ms 44152 KB Output is correct
8 Correct 44 ms 44152 KB Output is correct
9 Correct 43 ms 44152 KB Output is correct
10 Correct 43 ms 44152 KB Output is correct
11 Correct 43 ms 44152 KB Output is correct
12 Correct 43 ms 44152 KB Output is correct
13 Correct 42 ms 44152 KB Output is correct
14 Correct 43 ms 44160 KB Output is correct
15 Correct 44 ms 44152 KB Output is correct
16 Correct 42 ms 44152 KB Output is correct
17 Correct 43 ms 44152 KB Output is correct
18 Correct 41 ms 44156 KB Output is correct
19 Correct 44 ms 44152 KB Output is correct
20 Correct 42 ms 44152 KB Output is correct
21 Correct 41 ms 44280 KB Output is correct
22 Correct 43 ms 44152 KB Output is correct
23 Correct 47 ms 44152 KB Output is correct
24 Correct 43 ms 44152 KB Output is correct
25 Correct 42 ms 44152 KB Output is correct
26 Correct 45 ms 44152 KB Output is correct
27 Correct 42 ms 44280 KB Output is correct
28 Correct 44 ms 44152 KB Output is correct
29 Correct 48 ms 44152 KB Output is correct
30 Correct 43 ms 44152 KB Output is correct
31 Correct 44 ms 44152 KB Output is correct
32 Correct 43 ms 44152 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 44160 KB Output is correct
2 Correct 208 ms 53592 KB Output is correct
3 Correct 206 ms 53592 KB Output is correct
4 Correct 214 ms 53848 KB Output is correct
5 Correct 211 ms 53596 KB Output is correct
6 Correct 217 ms 53588 KB Output is correct
7 Correct 211 ms 53956 KB Output is correct
8 Correct 215 ms 53848 KB Output is correct
9 Correct 215 ms 53724 KB Output is correct
10 Correct 206 ms 53592 KB Output is correct
11 Correct 211 ms 53848 KB Output is correct
12 Correct 213 ms 53464 KB Output is correct
13 Correct 215 ms 53592 KB Output is correct
14 Correct 210 ms 53464 KB Output is correct
15 Correct 207 ms 53592 KB Output is correct
16 Correct 218 ms 53720 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 44160 KB Output is correct
2 Correct 306 ms 53096 KB Output is correct
3 Correct 307 ms 53140 KB Output is correct
4 Correct 370 ms 53224 KB Output is correct
5 Correct 295 ms 52964 KB Output is correct
6 Correct 310 ms 52952 KB Output is correct
7 Correct 297 ms 53076 KB Output is correct
8 Correct 320 ms 53276 KB Output is correct
9 Correct 316 ms 53080 KB Output is correct
10 Correct 299 ms 52928 KB Output is correct
11 Correct 357 ms 53208 KB Output is correct
12 Correct 299 ms 52952 KB Output is correct
13 Correct 386 ms 53208 KB Output is correct
14 Correct 308 ms 53116 KB Output is correct
15 Correct 306 ms 52956 KB Output is correct
16 Correct 291 ms 52884 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 77912 KB Output is correct
2 Correct 637 ms 79680 KB Output is correct
3 Correct 622 ms 80344 KB Output is correct
4 Correct 633 ms 79248 KB Output is correct
5 Correct 624 ms 79296 KB Output is correct
6 Correct 663 ms 79552 KB Output is correct
7 Correct 635 ms 80088 KB Output is correct
8 Correct 666 ms 80132 KB Output is correct
9 Correct 648 ms 79576 KB Output is correct
10 Correct 622 ms 80076 KB Output is correct
11 Correct 632 ms 79752 KB Output is correct
12 Correct 638 ms 80032 KB Output is correct
13 Correct 652 ms 79804 KB Output is correct
14 Correct 669 ms 79972 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 44160 KB Output is correct
2 Correct 44 ms 44152 KB Output is correct
3 Correct 45 ms 44152 KB Output is correct
4 Correct 43 ms 44152 KB Output is correct
5 Correct 42 ms 44152 KB Output is correct
6 Correct 42 ms 44152 KB Output is correct
7 Correct 43 ms 44152 KB Output is correct
8 Correct 44 ms 44152 KB Output is correct
9 Correct 43 ms 44152 KB Output is correct
10 Correct 43 ms 44152 KB Output is correct
11 Correct 43 ms 44152 KB Output is correct
12 Correct 43 ms 44152 KB Output is correct
13 Correct 42 ms 44152 KB Output is correct
14 Correct 43 ms 44160 KB Output is correct
15 Correct 44 ms 44152 KB Output is correct
16 Correct 42 ms 44152 KB Output is correct
17 Correct 43 ms 44152 KB Output is correct
18 Correct 41 ms 44156 KB Output is correct
19 Correct 44 ms 44152 KB Output is correct
20 Correct 42 ms 44152 KB Output is correct
21 Correct 41 ms 44280 KB Output is correct
22 Correct 43 ms 44152 KB Output is correct
23 Correct 47 ms 44152 KB Output is correct
24 Correct 43 ms 44152 KB Output is correct
25 Correct 42 ms 44152 KB Output is correct
26 Correct 45 ms 44152 KB Output is correct
27 Correct 42 ms 44280 KB Output is correct
28 Correct 44 ms 44152 KB Output is correct
29 Correct 48 ms 44152 KB Output is correct
30 Correct 43 ms 44152 KB Output is correct
31 Correct 44 ms 44152 KB Output is correct
32 Correct 43 ms 44152 KB Output is correct
33 Incorrect 190 ms 53228 KB Output isn't correct
34 Halted 0 ms 0 KB -