oj.uz

Submission #199550

# Submission time Handle Problem Language Result Execution time Memory
199550 2020-02-02T02:31:25 Z arnold518 역사적 조사 (JOI14_historical) C++14
0 / 100
 4000 ms 612 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int SQ = 500;

int N, Q, A[MAXN+10], B[MAXN+10], S;
vector<int> comp;

struct Query
{
	int l, r, p;
	bool operator < (const Query &p)
	{
		if(l/SQ==p.l/SQ) return r<p.r;
		return l<p.l;
	}
};

Query query[MAXN+10];

ll tree[MAXN*4+10], ans[MAXN+10];
void update(int node, int tl, int tr, int pos, ll val)
{
	while(tl!=tr)
	{
		int mid=tl+tr>>1;
		if(pos<=mid) node>>=1, tr=mid;
		else node>>=1, node|=1, tl=mid+1;
	}
	tree[node]+=val;
	while(node!=1)
	{
		node>>=2;
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
}
ll qquery() { return tree[1]; }

void push(int x) { update(1, 1, S, B[x], A[x]); }
void pop(int x) { update(1, 1, S, B[x], -A[x]); }

int main()
{
	int i, j;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end()); S=comp.size();
	for(i=1; i<=N; i++) B[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
	for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;
	sort(query+1, query+Q+1);

	int l=1, r=1; push(1);
	for(i=1; i<=Q; i++)
	{
		while(r<query[i].r) r++, push(r);
		while(l>query[i].l) l--, push(l);
		while(r>query[i].r) pop(r), r--;
		while(l<query[i].l) pop(l), l++;
		ans[query[i].p]=qquery();
	}
	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message

historic.cpp: In function 'void update(int, int, int, int, ll)':
historic.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
historic.cpp: In function 'int main()':
historic.cpp:53:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
historic.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
historic.cpp:56:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
historic.cpp:60:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 612 KB Time limit exceeded
2 Halted 0 ms 0 KB -