Submission #50398

#TimeUsernameProblemLanguageResultExecution timeMemory
50398wzyFortune Telling 2 (JOI14_fortune_telling2)C++11
35 / 100
2023 ms277052 KiB
#include <bits/stdc++.h> using namespace std; int readint(){ char a = 255; int x = 0; while(!(a >= '0' && a <= '9'))a = getchar(); while(a >= '0' && a <= '9') x = 10*x + (a - '0') , a = getchar(); return x; } struct card{ int a , b; bool flip = false; } v[200005]; int n , k ; struct node{ node *left = NULL, *right = NULL; int rmqidx = -1; } ; node * treex ; void update(node *&tree , int x , int vl , int l = 0 , int r = 1000000007){ int mid = (l+r)/2; if(l == r){ tree->rmqidx = max(tree->rmqidx , vl); return ; } if(x <= mid){ if(tree->left == NULL) tree->left = new node(); update(tree->left , x , vl , l , mid); } else{ if(tree->right == NULL) tree->right = new node(); update(tree->right, x , vl , mid + 1, r); } int xl = -1 , xr = -1; if(tree->left != NULL) xl = tree->left->rmqidx; if(tree->right != NULL) xr = tree->right->rmqidx; tree->rmqidx = max(xl, xr); return ; } int query(node *&tree , int x , int y , int l = 0 , int r = 1000000007){ int mid = (l+r)/2; if(x == l && y == r){ return tree->rmqidx; } if(y <= mid){ if(tree->left == NULL) return -1; return query(tree->left, x , y , l, mid); } else if(x > mid){ if(tree->right == NULL) return -1; return query(tree->right , x , y, mid + 1 , r); } else{ int xl = -1 , xr = -1; if(tree->left != NULL) xl = query(tree->left, x , mid , l ,mid); if(tree->right != NULL) xr = query(tree->right , mid + 1 , y , mid + 1 , r); return max(xl, xr); } } struct nd{ nd *left = NULL , * right = NULL; int sj = 0; } ; nd * trees[200005]; int Uvl[200005]; void persistent(nd *& old_version , nd *& nw , int x , int vl , int l = 0 , int r = 1000000007){ int mid = (l+r)/2; if(l == r){ nw->sj = old_version->sj; nw->sj += vl; return ; } if(x <= mid){ nw->right = old_version->right; if(nw->left == NULL) nw->left = new nd(); if(old_version->left == NULL) persistent(trees[0] , nw->left , x , vl , l, mid); else persistent(old_version->left , nw->left, x , vl ,l ,mid); } else{ nw->left = old_version->left; if(nw->right == NULL) nw->right = new nd(); if(old_version->right == NULL) persistent(trees[0] , nw->right , x , vl , mid + 1 , r); else persistent(old_version->right , nw->right , x , vl , mid + 1 , r); } int a= 0 , b = 0; if(nw->left != NULL) a = nw->left->sj; if(nw->right != NULL) b = nw->right->sj; nw->sj = a + b; } int queryvl(nd *& treel , nd *& treer , int x , int y , int l = 0 , int r = 1000000007){ int mid = (l+r)/2; if(l == x && r == y){ return (treer->sj - treel->sj); } if(y <= mid){ if(treer->left == NULL) return 0; else{ if(treel->left == NULL) return queryvl(trees[0] , treer->left , x , y , l ,mid); else return queryvl(treel->left , treer->left , x , y , l ,mid); } } else if(x > mid){ if(treer->right == NULL) return 0; else{ if(treel->right == NULL) return queryvl(trees[0] , treer->right , x , y, mid + 1 , r); else return queryvl(treel->right , treer->right , x , y, mid+ 1 , r); } } else{ int a = 0 , b = 0; if(treer->left != NULL){ if(treel->left == NULL) a = queryvl(trees[0] , treer->left , x , mid , l , mid); else a = queryvl(treel->left , treer->left , x , mid , l, mid); } if(treer->right != NULL){ if(treel->right == NULL) b = queryvl(trees[0] , treer->right , mid +1 , y, mid +1 , r); else b = queryvl(treel->right , treer->right , mid + 1 , y , mid + 1 , r); } return (a+b); } } void dfs(node *& treex , int l = 0 , int r = 1000000007){ int mid = (l+r)/2; if(l == r){ delete treex; return ; } if(treex->left != NULL) dfs(treex->left, l ,mid); if(treex->right != NULL) dfs(treex->right , mid + 1 , r); return ; } int32_t main(){ n = readint() , k = readint(); for(int i = 0 ;i < n ; i ++){ v[i].a = readint() , v[i].b = readint(); if(v[i].a > v[i].b){ swap(v[i].a , v[i].b); v[i].flip = 1; } } treex = new node(); trees[0] = new nd(); queue<int> ww; for(int i = 0 ; i < k ; i++){ int x; x = readint(); ww.push(x); update(treex , x , i); } for(int i = 0 ; i < n; i ++){ if(v[i].a < v[i].b) Uvl[i] = query(treex , v[i].a , v[i].b - 1); else Uvl[i] = -1; } dfs(treex); for(int i = 0 ; i < k ; i++){ int x = ww.front(); ww.pop(); trees[i+1] = new nd(); persistent(trees[i] , trees[i+1] , x , +1); } long long ans = 0LL; int j =0; for(int i = 0 ; i < n ; i ++){ int U = Uvl[i]; if(U == -1){ int Z = queryvl(trees[0] , trees[k] , v[i].b , 1000000005); if(v[i].flip) Z += 1; if(Z%2){ ans += v[i].b; } else ans += v[i].a; } else{ int R = queryvl(trees[U] , trees[k] , v[i].b , 1000000005); if(R%2){ ans += v[i].a; } else ans += v[i].b; } } printf("%lld\n" , ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:174:6: warning: unused variable 'j' [-Wunused-variable]
  int j =0;
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...