In light of the recent results of the unfortunate competition professionals, I decided to increase the amount of devotion again. I would like to devote myself to solving problems beyond the water diff in time.
For the time being, I plan to solve the water diff ~ yellow diff problem by 1AC or more every day until all the S semester classes are over. I will do my best.
About an hour and a half (I will measure the time from now on)
It is $ O (NQ) $ when each person decides which road construction will be closed once, so ** It seems that it can be done efficiently if you think about which person will be closed for each road construction ** ..
Here, the i-th road construction closes people passing through the coordinates $ X_i $ between $ \ [S_i, T_i-1 ] $, but the coordinates can be summarized in time. In other words, walking at speed 1 can be rephrased as closing people who depart between $ \ [S_i-X_i, T_i-X_i-1 ] $.
The person who departs at the previous time can be searched by the binary search, so we will consider updating the section obtained by the binary search $ N $ times, but it is necessary to update the section efficiently. There is a delay segment tree as a data structure that efficiently updates sections, and in order to find the one with the closest coordinates in road construction that is closed to traffic, ** update in order from the one with the farthest coordinates **. I thought. However, I avoided this solution because I had never used a delayed segment tree and was afraid to bug it.
Here, ** the important thing in interval update is to save only both ends and think cumulatively at the end ** (same for imos method and delayed segment tree). Therefore, ** ans_sectl [i]: deque ** that stores the index of the section where the i-th person is on the left end, and ** ans_sectr [i]: the index of the section where the i-th person is on the right end. Prepare a deque ** to save. (I chose $ \ because $ deque because it can be retrieved with $ O (1) $.)
Also, although it is reprinted, ** the one with the closest coordinates in the road construction that is closed is actually closed **, so when you first receive $ S_i, T_i, X_i $, the value of $ X_i $ is used in ascending order. Sort it (xst). … ①
Under this, a container (ʻans) that stores ** an index of the section containing each person's departure time ** (= an index of road construction that may be closed to each person) If you prepare and repeat ʻinsert if it is included in ʻans_sectl and ʻerase if it is included in ʻans_sectr in order from the person with the smallest number, ʻans will behave as fast as you want. To.
Furthermore, the index of the section included in ʻans is saved in ascending order if it is a ** C ++ map or set **, and it should be obtained because the road construction has the closest coordinates included in ʻans, so the beginning of the container. All you have to do is output the distance of the closed point corresponding to the element of ($ \ because $ ①).
Also, when finding a person whose departure time is included in $ \ [S_i-X_i, T_i-X_i-1 ] $ in a closed interval, the left end is L = (lower_bound (ALL (d), sx)- You need to find the right end with R = (upper_bound (ALL (d), tx-1) -d.begin ())-1 with d.begin (), but $ \ [S_i-X_i, T_i If there is no one whose departure time is included in -X_i-1 ] $, then $ L> R $, so you need to exclude this case.
abc128e.cc
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() //I want to omit arguments such as sort
#define SIZE(x) ll(x.size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
#define Umap unordered_map
#define Uset unordered_set
//The processing at the end was sloppy, this kind of loose implementation is useless
signed main(){
//Code for speeding up input
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,be careful upper
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
map<ll,ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans[*(ans_sectl[i].begin())]+=1;
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[ans.begin()->F][0]<<"\n";
}
REP(_,sr){
ans[*(ans_sectr[i].begin())]-=1;
if(ans[*(ans_sectr[i].begin())]==0)ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
abc128e_set.cc
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() //I want to omit arguments such as sort
#define SIZE(x) ll(x.size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
#define Umap unordered_map
#define Uset unordered_set
//The processing at the end was sloppy, this kind of loose implementation is useless
signed main(){
//Code for speeding up input
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,be careful upper
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
set<ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans.insert(*(ans_sectl[i].begin()));
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[*ans.begin()][0]<<"\n";
}
REP(_,sr){
ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
About 1 hour (I will measure the time from now on)
I was solving a problem that became more difficult by ** misreading ** "doing up to K times" as "just doing K times". It's no good ...
First of all, $ N $ and $ K $ are not very large, so it is necessary to understand that there seems to be some margin in the amount of calculation.
Here, I will first try the method of greedily taking from the outer high-value gemstone, but reject it because ** there may be high-value gemstone inside **. Also, if you perform the operation to take out on the same side after the ** packing operation, the two operations are useless , so you can see that you should perform the packing operation after performing the taking out operation ( operation Swap to make it easier to think! **).
Here, if you decide the number of times to take out, the number of times to pack is also decided, so I decided to decide the number of times to take out $ i $ (the first ** misreading ** caused the policy to start straying around here, ** I had to calm down and read the question **.). If $ i $ is 0, the packing operation cannot be performed and the maximum value of the total value of the gemstones after the operation is 0, so $ i $ is considered from 1 to $ min (k, n) $. Also, even when the number of operations to take out is $ i $, I thought that I would greedily take the gems with the highest value on the outside **, but there may be gems with the highest value on the inside **, so this policy Will be rejected.
Therefore, in addition to the fact that there is still room for calculation, I tried all $ m $ when extracting $ m $ from the left and $ im $ from the right ($ m = 0 $ ~ $ i). What is taken out with $ is sliced and stored in the array $ s $). Also, since it is good to pack the extracted items in order from the one with the lowest value ** (however, the value is 0 or less), sort $ s $ and pack up to $ min (ki, i) $ times. It's fine. In addition, it is a candidate for the maximum value that the sum of $ s $ can be calculated with 0 as the packed item.
With the above, the amount of calculation is $ O (X ^ 3 \ log {X}) $ with $ X = min (N, K) $, and there is no need to speed up any more, so implement it as follows. ..
abc128d.py
import math
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
#It was up to k times-misread
ans=0
for i in range(1,min(k,n)+1):
#Where to take(Isn't it always the bigger one?)
for m in range(i+1):
s=v[:m]+v[n-(i-m):]
s.sort()
#Don't try to pack more than you took!
#Remaining k-i times
for j in range(i,min(k,2*i)):#If you can't pack any more
#Rewrite if less than 0
if s[j-i]<0:s[j-i]=0
#The biggest one I took out(0 to return)
ans=max(ans,sum(s))
#Remaining k-j times(I didn't do j at the time of break)
#From here, repeat putting in and putting out a good feeling(If it is an even number, is it as it is?)
#You don't even need it, you don't have to use up k times
#print(sum(s))
print(ans)
I didn't have a lot of time this time, but I solved it in about an hour in total.
Of the two conditions, I considered $ a + b = a \ oplus b $, which is easy to think about. This can be understood with a little thought, but $ XOR $ is ** $ \ leftrightarrow $ ** where each bit can be calculated independently ** There is no carry in binary calculation **, so a and b are optional You can see that there are only three sets of (0,1), (1,0), (0,0) for the bits of. … ①
Under this, the first condition $ a + b \ leqq L $ is processed, but here we have to think that "if the first digit is 0 or 1, if the second digit is 0 or 1, ..." I was sloppyly thinking, "If it falls below some digit, then any digit after that is fine." However, it has been a long time since the idea of ** digit DP ** applies to problems with such patterns. I remembered it after that ...
ARMERIA's article and [Kenchon's article](https://drken1215.hatenablog.com/entry/2019/ If you refer to 02/04/013700), it can be generalized that the digit DP can be used if there are the following two properties.
1: ** I want to find the number of values (maximum and minimum values of XX) that satisfy XX below the upper limit $ L $ ** (and $ L $ is large) 2: There is a condition regarding digits
Under this, the state of DP can be determined as follows. $ DP [i] [smaller]: = $ Some value when determining from the top to the $ i $ digit (However, when ** $ smaller = 0 $, there are digits smaller than $ L $ up to the $ i $ digit, and when $ smaller = 1 $, all digits up to the ith digit are $ L $. It can be said that it is the same as **.)
In addition, ** DP transitions are as follows each time **. ・ Only $ DP [i + 1] [0] $ transitions from $ DP [i] [0] $, and any $ i $ digit can be selected. -In the transition from $ DP [i] [1] $ to $ DP [i + 1] [0] $, the $ i $ digit can be selected from all numbers smaller than the $ i $ digit of $ L $. it can. -In the transition from $ DP [i] [1] $ to $ DP [i + 1] [1] $, the $ i $ digit must be the same as the $ i $ digit of $ L $.
If you confirm the movement of the digit DP with the above, this problem is simple, and you can determine the state of DP as follows.
$ DP [i] [smaller]: = $ Number of pairs of $ (a, b) $ when determining from the top to the $ i $ bit (However, when $ smaller $ is 0, bits smaller than $ L $ exist in $ a + b $ from the top to the $ i $ bit, and when $ smaller $ is 1, $ i $ bits from the top exist. All bits up to the eye are equal to $ L $)
In addition, there are three types of DP transitions (\ because $ ① $).
・ $ DP [i + 1] [0] = 3 × DP [i] [0] \ ($ i $ bit of \ because a + b $ can be 0 or 1 $) $ ・ When the $ i + 1 $ digit of $ L $ is 0 $ DP [i + 1] [1] = DP [i] [1] \ (\ because a + b $'s $ i $ bit has only 0 $) $ ・ When the $ i + 1 $ digit of $ L $ is 1. $ DP [i + 1] [0] = DP [i] [1] \ (\ because a + b $ when the $ i $ bit is 0, $ (a $ and $ b $ i-bit $) ) = (0,0)) $ $ DP [i + 1] [1] = 2 * DP [i] [1] \ (\ because a + b $ $ i $ bit When the first is 1, $ (a $ and $ b $ i bits) Eye $) = (0,1), (1,0)) $
The code below implements this transition. The game was to be able to come up with a digit DP immediately, so I should have solved it a little more. It is mortifying.
abc129e.py
mod=10**9+7
l=input()
bit=[int(i) for i in l]
m=len(bit)
#I overdo it properly, but the digit DP
#Same as the smaller one
dp=[[0,0] for i in range(m)]
dp[0]=[1,2]
for i in range(m-1):
dp[i+1][0]=3*dp[i][0]%mod
if bit[i+1]==0:
dp[i+1][1]+=dp[i][1]
dp[i+1][1]%=mod
else:
dp[i+1][0]+=dp[i][1]
dp[i+1][1]+=(2*dp[i][1])
dp[i+1][0]%=mod
dp[i+1][1]%=mod
print(sum(dp[m-1])%mod)
Recommended Posts