oj.uz

Submission #535280

# Submission time Handle Problem Language Result Execution time Memory
535280 2022-03-09T21:46:05 Z fadi57 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 94 ms 28716 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int mx= 700 * 1000 + 3;
const int mx2=1e6+9;
typedef long long ll;
const int mod=998244353 ;
const int SQ=400;
const ll inf=1e9+10;
vector<int>cord,q[mx];
int seg[mx<<2],a[mx],b[mx],T[mx],aa[mx], bb[mx];
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s;
int sz;int t;int n,k;
int combin(int x,int y){
  if(t==0){
    return (max(x,y));
  }else{
    return x+y;
  }

}
void update(int node,int l,int r,int idx,int val){
   if(l==r){
    seg[node]=val;
    return;
   }
    int mid=(l+r)/2;
    if(idx<=mid){
    update(node*2,l,mid,idx,val);
   }else{
    update(node*2+1,mid+1,r,idx,val);
   }
   seg[node]=combin(seg[node*2],seg[node*2+1]);
    return;
  }
  int query(int node,int l,int r,int left,int right){
         if(r<left||l>right){
            if(t){return 0;}
            return -1;
      }
  if(l>=left&&r<=right){
        return seg[node];
     }
     int mid=(l+r)/2;
     return combin(query(node*2,l,mid,left,right), query(node*2+1,mid+1,r,left,right));
     }


int fin(int x){
  return upper_bound(cord.begin(),cord.end(),x)-cord.begin();
  }

 int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    aa[i]=a[i];
    bb[i]=b[i];
    cord.push_back(a[i]);
    cord.push_back(b[i]);
  }
for(int i=0;i<k;i++){
     cin>>T[i];
     cord.push_back(T[i]);
  }

cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;
   sort(cord.begin(),cord.end());
sz=cord.size()+5;
for(int i=0;i<n;i++){
    a[i]=fin(a[i]);
   b[i]=fin(b[i]);
  }  memset(seg,-1,sizeof(seg));
    for(int i=0;i<k;i++){
    T[i]=fin(T[i]);
    update(1,0,sz,T[i],i);
    }
  for(int i=0;i<n;i++){
    int idx=query(1,0,sz,min(a[i],b[i]),max(a[i],b[i])-1);
     q[idx+1].push_back(i);
    }
t=1;ll ans=0;
   memset(seg,0,sizeof(seg));
  for (int i=k;i>=0;i--)
	{if(i!=k){ update(1,0,sz,T[i],1);}

		for (int j:q[i])
		{
			int parity;
			parity=query(1,0,sz,max(a[j],b[j]),sz)%2;
		if(i==0)
    		parity ^= a[j] < b[j];
         if(parity){
            ans+=min(bb[j],aa[j]);
           //   cout<<min(bb[j],aa[j])<<endl;
         }else{
          ans+=max(bb[j],aa[j]);
         // cout<<max(bb[j],aa[j])<<endl;
          }
    	//cout<<i<<" "<<j<<" "<<parity<<"\n";


		}

}

   cout<<ans;

  }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 16 ms 27708 KB Output is correct
4 Correct 16 ms 27760 KB Output is correct
5 Correct 15 ms 27712 KB Output is correct
6 Correct 16 ms 27732 KB Output is correct
7 Correct 16 ms 27688 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 18 ms 27748 KB Output is correct
10 Correct 14 ms 27732 KB Output is correct
11 Correct 16 ms 27732 KB Output is correct
12 Correct 16 ms 27732 KB Output is correct
13 Correct 17 ms 27732 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 16 ms 27708 KB Output is correct
4 Correct 16 ms 27760 KB Output is correct
5 Correct 15 ms 27712 KB Output is correct
6 Correct 16 ms 27732 KB Output is correct
7 Correct 16 ms 27688 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 18 ms 27748 KB Output is correct
10 Correct 14 ms 27732 KB Output is correct
11 Correct 16 ms 27732 KB Output is correct
12 Correct 16 ms 27732 KB Output is correct
13 Correct 17 ms 27732 KB Output is correct
14 Correct 42 ms 28072 KB Output is correct
15 Correct 66 ms 28480 KB Output is correct
16 Incorrect 94 ms 28716 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 16 ms 27708 KB Output is correct
4 Correct 16 ms 27760 KB Output is correct
5 Correct 15 ms 27712 KB Output is correct
6 Correct 16 ms 27732 KB Output is correct
7 Correct 16 ms 27688 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 18 ms 27748 KB Output is correct
10 Correct 14 ms 27732 KB Output is correct
11 Correct 16 ms 27732 KB Output is correct
12 Correct 16 ms 27732 KB Output is correct
13 Correct 17 ms 27732 KB Output is correct
14 Correct 42 ms 28072 KB Output is correct
15 Correct 66 ms 28480 KB Output is correct
16 Incorrect 94 ms 28716 KB Output isn't correct
17 Halted 0 ms 0 KB -