oj.uz

Submission #535263

# Submission time Handle Problem Language Result Execution time Memory
535263 2022-03-09T20:46:11 Z fadi57 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 1375 ms 10056 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=2e5+900;
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[4*mx],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){

    seg[idx]=val;
    return;
   if(l==idx){
    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){
       int z=-1;
      if(t==0){

        for(int i=left;i<=right;i++){
            z=max(z,seg[i]);

        }
      }else{
         z=0;
         for(int i=left;i<=right;i++){
            z+=seg[i];

        }
      }
      return z;
      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));
     }

    void upd(int pos,int val){
       update(1,0,sz,pos,val);

    }
    int quer(int x,int y){
       return query(1,0,sz,x,y);

     }

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]);
  }

  sort(cord.begin(),cord.end());
  cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;


 sz=cord.size();
    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]);
    upd(T[i],i);
  //  cout<<T[i];
    }

   for(int i=0;i<n;i++){

     int idx=quer(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--)
	{
        upd(T[i],1);
		for (int j:q[i])
		{
			int parity;
			parity=quer(max(a[j],b[j]),sz)&1;
			if(i==0)
    			parity ^= a[j] < b[j];
         if(parity){
            ans+=min(bb[j],aa[j]);
         }else{
          ans+=max(bb[j],aa[j]);
          }
    		//ans += parity ? max(bb[i],aa[i]):min(bb[i],aa[i]);
    	//	cout<<i<<" "<<j<<" "<<parity<<"\n";

		}

		//cout<<seg[3]<<endl;

	}

   cout<<ans;

  }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 6 ms 8240 KB Output is correct
6 Correct 7 ms 8240 KB Output is correct
7 Correct 6 ms 8236 KB Output is correct
8 Correct 8 ms 8268 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 6 ms 8236 KB Output is correct
13 Correct 6 ms 8240 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 6 ms 8240 KB Output is correct
6 Correct 7 ms 8240 KB Output is correct
7 Correct 6 ms 8236 KB Output is correct
8 Correct 8 ms 8268 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 6 ms 8236 KB Output is correct
13 Correct 6 ms 8240 KB Output is correct
14 Correct 173 ms 8904 KB Output is correct
15 Correct 628 ms 9492 KB Output is correct
16 Incorrect 1375 ms 10056 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 6 ms 8240 KB Output is correct
6 Correct 7 ms 8240 KB Output is correct
7 Correct 6 ms 8236 KB Output is correct
8 Correct 8 ms 8268 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 6 ms 8236 KB Output is correct
13 Correct 6 ms 8240 KB Output is correct
14 Correct 173 ms 8904 KB Output is correct
15 Correct 628 ms 9492 KB Output is correct
16 Incorrect 1375 ms 10056 KB Output isn't correct
17 Halted 0 ms 0 KB -