Submission #320937

#	Time	Username	Problem	Language	Result	Execution time	Memory
320937		egas	Pilot (NOI19_pilot)	C++14	0 / 100	22 ms	5352 KiB

pilot

#include <bits/stdc++.h>

using namespace std;
long LOG[1005];
long POWW[31];
class SparseTable {
    private:
	long lookup[1005][(long) log2l(1005) + 1];
	
    void buildSparseTable(long arr[], long n) {
        for (long i = 0; i < n; i++)
            lookup[i][0] = arr[i];
        for (long j = 1;
            (1 << j) <= n; j++) {
            for (long i = 0;
                (i + (1 << j) - 1) < n; i++) {
                if (lookup[i][j - 1] > lookup[i + (1 << (j - 1))][j - 1])
                    lookup[i][j] = lookup[i][j - 1];
                else
                    lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    public:    
    
    SparseTable(vector < long > & a) {
        long num[a.size()];
        for (long i = 0; i < a.size(); i++) {
            num[i] = a[i];
        }
        buildSparseTable(num, a.size());
    }
        
    long query(long L, long R) {
        L--;
        R--;
        long j = LOG[R - L + 1];
        if (lookup[L][j] >= lookup[R - POWW[j] + 1][j])
            return lookup[L][j];
        else
            return lookup[R - POWW[j] + 1][j];
    }
};


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long n;
    cin >> n;
    long m;
    cin >> m;
    
    vector < long > a(n);
    for (long i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector < long > b(m);
    for (long i = 0; i < m; i++) {
        cin >> b[i];
    }
    
    for (int i = 0; i < 1005; i++) {
        LOG[i] = (long) log2l(i);
    }
    
    for (int i = 0; i < 31; i++) {
        POWW[i] = powl(2, i);
    }
    
    vector < long > diff(1005, 0);
    SparseTable ST(a);
    
    long * last = new long[1005];
    long * frnt = new long[1005];
    for (long i = 0; i < a.size(); i++) {
        last[a[i]] = -1;
        frnt[a[i]] = n;
    }
    
    for (long i = 0; i < n; i++) {
        long ryt = 0;
        long l = i;
        long r = a.size() - 1;
        if(i-1>=0 and a[i-1]>a[i]){
        	r=frnt[i-1];
        }
        while (l <= r) {
            if (l == r) {
                if (ST.query(i + 1, l + 1) <= a[i]) {
                    ryt = max(ryt, l);
                }
                break;
            }
            long m = (l + r) / 2;
            if (ST.query(i + 1, m + 1) > a[i]) {
                r = m - 1;
            } else {
                l = m + 1;
                ryt = max(ryt, m);
            }
        }
        frnt[i]=ryt;
        ryt = ryt - i + 1;
        ryt--;
        
        
        long left = 1e9;
        l = last[a[i]] + 1;
        r = i;
        while (l <= r) {
            if (l == r) {
                if (ST.query(l + 1, i + 1) <= a[i]) {
                    left = min(left, l);
                }
                break;
            }
            long m = (l + r) / 2;
            if (ST.query(m + 1, i + 1) > a[i]) {
                l = m + 1;
            } else {
                r = m - 1;
                left = min(left, m);
            }
        }
        left = i - left;
        last[a[i]] = i;
        diff[a[i]] += ((left + 1) * (ryt + 1));
    }
    
    for (long i = 1; i < diff.size(); i++) {
        diff[i] += diff[i - 1];
    }
    
    for (long i = 0; i < b.size(); i++) {
        cout << diff[b[i]] << '\n';
    }
    return 0;
}

Compilation message (stderr)

pilot.cpp: In constructor 'SparseTable::SparseTable(std::vector<long int>&)':
pilot.cpp:29:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (long i = 0; i < a.size(); i++) {
      |                          ~~^~~~~~~~~~
pilot.cpp: In function 'int32_t main()':
pilot.cpp:78:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (long i = 0; i < a.size(); i++) {
      |                      ~~^~~~~~~~~~
pilot.cpp:133:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (long i = 1; i < diff.size(); i++) {
      |                      ~~^~~~~~~~~~~~~
pilot.cpp:137:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (long i = 0; i < b.size(); i++) {
      |                      ~~^~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 5
• Subtask 6: 0 / 9
• Subtask 7: 0 / 14
• Subtask 8: 0 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11